【Leetcode】268. Missing Number

Description

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

For example,
Given nums = [0, 1, 3] return 2.

Note

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

Solution

public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        if (nums[0] != 0) {
            return 0;
        }
        int len = nums.length;
        if (nums[len - 1] != len) {
            return len;
        }
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] != 1) {
                return (nums[i] - 1);
            }
        }
        return 0;
    }

Result

AC

Analyse

排除了数组头和尾部之后，就是如果相差不为1，那么就可以找出这个值。

Optimization

First

public int missingNumber(int[] nums) {
        int xor = 0, i = 0;
        for (i = 0; i < nums.length; i++) {
            xor = xor ^ i ^ nums[i];
        }
        return xor ^ i;
    }

Analyse

这个方法很好，需要熟悉异或的知识，首先，相同的数字异或肯定0，如果开始没有改变，那么i ^ nums[i]肯定是0，xor一直为0，在最后返回值的i肯定是nums的length，在这里可以，如果中间丢了一位，那么肯定nums[i]和后面的i相等，这样也都可以抵消，最后一个数，也可以在返回那里和nums.length抵消，这样剩下的肯定就是开始的0和中间丢失的数字，那么就是那个i丢失，就是返回这个结果。

Second

public int missingNumber(int[] nums) {
        int len = nums.length;
        int sum = len * (len + 1) / 2;
        for (int i = 0; i < len; i++) {
            sum -= nums[i];
        }
        return sum;
    }

Analyse

思路简单清晰，但是这个肯定不会是面试官只要的答案。

Third

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

Analyse

二分法，一定要熟练。