題目描述

一個(gè)長(zhǎng)度為n-1的遞增排序數(shù)組中的所有數(shù)字都是唯一的，并且每個(gè)數(shù)字都在范圍0～n-1之內(nèi)。在范圍0～n-1內(nèi)的n個(gè)數(shù)字中有且只有一個(gè)數(shù)字不在該數(shù)組中，請(qǐng)找出這個(gè)數(shù)字。

題解

這道題目有兩個(gè)比較直觀的解，一個(gè)方法是從0開(kāi)始順序遍歷數(shù)組，如果發(fā)現(xiàn)哪個(gè)位置不連續(xù)了，則找到這個(gè)數(shù)字。另一個(gè)方法是將0 ~ n-1 的和減去數(shù)組的和，得到的結(jié)果就是缺失的數(shù)字。這兩種方法的時(shí)間復(fù)雜度都是O(n)。

其實(shí)時(shí)間復(fù)雜度為O(logn)的的二分法也是比較容易想到的，來(lái)看代碼。

class Solution {
    public int missingNumber(int[] nums) {
        int left = 0, right = nums.length-1, mid;
        while (left < right) {
            mid = (left + right) >> 1;

            // 說(shuō)明沒(méi)有問(wèn)題，缺失的數(shù)字在mid右邊
            if (mid == nums[mid]) {
                left = mid + 1;
            }
            // 說(shuō)明缺失的數(shù)字在mid左邊
            else if (mid < nums[mid]) {
                right = mid - 1;
            }
        }
        // 最終缺失的數(shù)字要么在left左邊，要么在left右邊
        if (left < nums[left])
            return nums[left] - 1;
        return nums[left] + 1;
    }
}