LeetCode 268. Missing Number

[Woodyiiiiiii]

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

---

自己首先想到的想法是根据和运算求得差值：

class Solution {
    public int missingNumber(int[] nums) {
        int len = nums.length;
        int max = len + 1, sum = 0;
        for (int num : nums) {
            sum += num;
        }
        
        return (max * (max - 1) ) / 2 - sum;
    }
}

第二种解法是利用位运算，同Similar Number系列一样，利用异或的特点——相等数异或为0的特点，将“残缺”数组和完整数组每个数字异或，最后的结果就是Missing Number。

class Solution {
    public int missingNumber(int[] nums) {
        int res = 0, i = 1;
        for (int num : nums) {
            res ^= num ^ i++;
        }
        
        return res;
    }
}

第三种解法是二分查找法。首先要排序，那么显然时间复杂度不是线性级别了，但如果给定的数组是已经排好序的，这个方法就很好用。

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums, 0, nums.length);
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > mid) right = mid - 1;
            else left = mid + 1;
        }
        
        return left;
    }
}

---

参考资料:

1. LeetCode原题
2. grandyang解法