Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3] return 2.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Sum, O(n) time, O(1) space
1
2
3
4
5
6
7
8
9
10
11
| public class Solution {
public int missingNumber(int[] nums) {
if (nums == null || nums.length == 0) return -1;
int length = nums.length;
int sum = (0 + length) * (length + 1) / 2;
for (int i = 0; i < length; i++){
sum -= nums[i];
}
return sum;
}
}
|
Bit, O(n) time, O(1) space
1
2
3
4
5
6
7
8
9
10
| public class Solution {
public int missingNumber(int[] nums) {
if (nums == null || nums.length == 0) return -1;
int xor = 0;
for (int i = 0; i < nums.length; i++){
xor = xor ^ i ^ nums[i];
}
return xor ^ nums.length;
}
}
|
Binary Search, O(n log n) time, O(1) space
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| public class Solution {
public int missingNumber(int[] nums) {
if (nums == null || nums.length == 0) return -1;
Arrays.sort(nums);
int start = 0, end = nums.length;
int mid = (start + end) / 2;
while (start < end){
if (nums[mid] == mid){
start = mid + 1;
}else{
end = mid;
}
mid = (start + end) / 2;
}
return start;
}
}
|