Comment on page

# 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.
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) {
}
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;
}
}