268. Missing Number.md

268. Missing Number

Question

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

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

Thinking:

• Method 1:

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

• Method 2:
  • 求出期望的和，减去每个元素。

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

Second time

1. We first get the sum of the array and the missing value is the deduction between expect sum and sum.

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

Third Time

• Method 1: Another method to find missing number in a sorted array.

   class Solution {
   	public int missingNumber(int[] nums) {
   		Arrays.sort(nums);
   		int low = 0, high = nums.length - 1;
   		return binarySearch(nums, low, high);
   	}
   	private int binarySearch(int[] nums, int low, int high){
   		int mid = low + (high - low) / 2;
   		if(nums[mid] == mid && nums[mid + 1] != mid + 1) return mid + 1;
   		else if(nums[mid] != mid){
   			return binarySearch(nums, low, mid - 1);
   		}else{
   			return binarySearch(nums, mid + 1, high);
   		}
   	}
   }