剑指 Offer 53 - II. 0～n-1中缺失的数字

Iterate

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int missingNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (i != nums[i]) {
                return i;
            }
        }

        return nums.length;
    }
}

XOR

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int missingNumber(int[] nums) {
        int res = 0;

        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i];
            res ^= i;
        }
        res ^= nums.length;

        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int missingNumber(int[] nums) {
        // 寻找首个索引与元素值不匹配的索引
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] == mid) {
                left = mid + 1;
            } else {
                // 可能是我们要找的索引，继续向左侧搜索
                right = mid - 1;
            }
        }

        // right, left, 此时 right 可能已经不符合条件，取 left
        return left;
    }
}

References

剑指 Offer 53 - II. 0～n-1中缺失的数字
面试题53 - II. 0～n-1 中缺失的数字（二分法，清晰图解）