268. Missing Number

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?

思路1: 用bit XOR来做,由于给定数组的特殊性,每个数字在数组中都有与下标相对应的数
复杂度: Time O(n)

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

思路2: 先排序,然后用二分法找到第一个和nums[i]不相等的数i就可以了。
复杂度: Time O(nlogn)

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

    }

思路3: 求和相减.
复杂度: Time O(n)

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s