268.Missing-Number

268. Missing Number

题目地址

https://leetcode.com/problems/missing-number/

题目描述

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?

代码

Approach #1 Sorting

class Solution {
  public int missingNumber(int[] nums) {
        Arrays.sort(nums);
    // 因为失去了一个元素，最后一个元素应为 nums.length
    if (nums[nums.length - 1] != nums.length) {
      return nums.length;
    } 
    // Ensure that 0 is at the first index
    else if (nums[0] != 0){
      return 0;
    }

    for (int i = 1; i < nums.length; i++) {
      int expectedNum = nums[i - 1] + 1;
      if (nums[i] != expectedNum) {
        return expectedNum;
      }
    }

    return -1;
  }
}

Approach #2 HashSet

class Solution {
  public int missingNumber(int[] nums) {
    Set<Integer> numSet = new HashSet<Integer>();
    for (int num: nums) {
      numSet.add(num);
    }

    int expectedNumCount = nums.length + 1;
    for (int number = 0; number < expectedNumCount; number++) {
      if (!numsSet.contains(number)) {
        return number;
      }
    }

    return -1;
  }
}

Approach #3 Bit Mannipulation

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

    return missing;
  }
}

Approach #4 Gauss' Formula

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