這是悅樂(lè)書的第297次更新，第316篇原創(chuàng)

01 看題和準(zhǔn)備

今天介紹的是LeetCode算法題中Easy級(jí)別的第165題（順位題號(hào)是704）。給定n個(gè)元素的排序（按升序）整數(shù)數(shù)組nums和目標(biāo)值，編寫一個(gè)函數(shù)來(lái)搜索nums中的目標(biāo)。如果target存在，則返回其索引，否則返回-1。例如：

輸入：nums = [-1,0,3,5,9,12]，目標(biāo)= 9

輸出：4

說(shuō)明：9存在于nums中，其索引為4


輸入：nums = [-1,0,3,5,9,12]，target = 2

輸出：-1

說(shuō)明：2在nums中不存在，因此返回-1


注意：

• nums中的所有元素都是唯一的。

• n將在[1,10000]范圍內(nèi)。

• nums中每個(gè)元素的值將在[-9999,9999]范圍內(nèi)。

本次解題使用的開發(fā)工具是eclipse，jdk使用的版本是1.8，環(huán)境是win7 64位系統(tǒng)，使用Java語(yǔ)言編寫和測(cè)試。

02 第一種解法

使用二分查找。取數(shù)組的第一位和最后一位索引值，計(jì)算取出中間數(shù)做新索引，判斷新索引對(duì)應(yīng)的元素是否等于目標(biāo)值，等于就直接返回新索引，小于就將開始索引重新賦值為中間索引加1，大于就將結(jié)束索引重新賦值為中間索引減1。

此解法的時(shí)間復(fù)雜度是O(log2(n))，空間復(fù)雜度是O(1)。

public int search(int[] nums, int target) {
    if (target < nums[0] || target > nums[nums.length-1]) {
        return -1;
    }
    int start = 0, end = nums.length-1;
    while (start <= end) {
        int mid = (end+start)/2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            end = mid-1;
        } else {
            start = mid+1;
        }
    }
    return -1;
}

03 第二種解法

直接使用循環(huán)依次匹配，如果遍歷完數(shù)組所有元素都沒(méi)有匹配上，就返回-1。

此解法的時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度是O(1)。

public int search(int[] nums, int target) {
    if (target < nums[0] || target > nums[nums.length-1]) {
        return -1;
    }
    for (int i=0; i<nums.length; i++) {
        if (target == nums[i]) {
            return i;
        }
    }
    return -1;
}

04 第三種解法

因?yàn)閿?shù)組元素的取值范圍定了，我們可以使用新的數(shù)組，以舊數(shù)組元素值為索引，舊元素索引為值，最后以目標(biāo)值為索引，在新數(shù)組中查找，如果其值為0，就返回-1，反之返回其值。

此解法的時(shí)間復(fù)雜度是O(n)，空間復(fù)雜度是O(n)。

public int search(int[] nums, int target) {
    if (target < nums[0] || target > nums[nums.length-1]) {
        return -1;
    }
    int[] temp = new int[20000];
    for (int i=0; i<nums.length; i++) {
        temp[nums[i]+10000] = i+1;
    }
    return temp[target+10000] == 0 ? -1 : temp[target+10000]-1; 
}

05 小結(jié)

算法專題目前已日更超過(guò)四個(gè)月，算法題文章165+篇，公眾號(hào)對(duì)話框回復(fù)【數(shù)據(jù)結(jié)構(gòu)與算法】、【算法】、【數(shù)據(jù)結(jié)構(gòu)】中的任一關(guān)鍵詞，獲取系列文章合集。

以上就是全部?jī)?nèi)容，如果大家有什么好的解法思路、建議或者其他問(wèn)題，可以下方留言交流，點(diǎn)贊、留言、轉(zhuǎn)發(fā)就是對(duì)我最大的回報(bào)和支持！