Missing Number
LeetCode.268. Missing Number Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
Example:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers,
so all numbers are in the range [0,9].
8 is the missing number in the range since it does not appear in nums.
方法1.排序：在循环数组，看后一个数是不是比前一个大1
方法2.哈希表：将数组中的元素插入哈希表，然后循环0～nums.length-1中的数是不是都在哈希表中
方法3.求和：0～nums.length-1求和减去nums中的和
方法4.位运算
First Solution
public static int missingNumber(int[] nums) {
int index = 0;
int n = nums.length;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i <= n; i++) {
map.put(i, 0);
}
for (int i = 0; i < n; i++) {
if (map.get(nums[i]) != null) {
map.remove(nums[i]);
}
}
for (Integer i:map.keySet()) {
index = i;
}
return index;
}
Better Solution
public int missingNumber(int[] nums) {
int missing = nums.length;
for (int i = 0; i < nums.length; i++) {
missing ^= i ^ nums[i];
}
return missing;
}
相同的数异或为0，时间复杂度
O(n)，空间复杂度O(1)