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;
 }
}