268. Missing Number

  • 43.9%

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

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

1
2
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?


方法一:

位运算

美团面试遇到过

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int res = 0;
for(int i=1; i<=n; i++){
res ^= nums[i-1];
res ^= i;
}
return res;
}
};

https://discuss.leetcode.com/topic/22313/c-solution-using-bit-manipulation

C++ solution using bit manipulation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int missingNumber(vector<int>& nums) {
int result = nums.size();
int i=0;

for(int num:nums){
result ^= num;
result ^= i;
i++;
}

return result;
}
};

There are several similar problems in the problem list.


https://discuss.leetcode.com/topic/22305/1-lines-ruby-python-java-c

1+ lines Ruby, Python, Java, C++

Several different solutions, some with O(1) extra space, some with O(n).

Sum of 0..n minus sum of the given numbers is the missing one.

These only use O(1) extra space.

Python

1
2
3
def missingNumber(self, nums):
n = len(nums)
return n * (n+1) / 2 - sum(nums)

Java

1
2
3
4
public int missingNumber(int[] nums) {
long n = nums.length;
return (int) (n * (n+1) / 2 - IntStream.of(nums).sum());
}

C++

1
2
3
4
int missingNumber(vector<int>& nums) {
long n = nums.size();
return n * (n+1) / 2 - accumulate(begin(nums), end(nums), 0);
}

Using long for Java and C++ to prevent overflow (the n*(n+1) overflows ints already for n=46341, and then the /2 causes an actual wrong result).

Xor-ing the given numbers and 0..n.

These use O(n) extra space, but I like them anyway.

Python

1
2
def missingNumber(self, nums):
return reduce(operator.xor, nums + range(len(nums)+1))

Xor-ing with O(1) space

Saw this from ts before. Xoring 0..n results in [n, 1, n+1, 0][n % 4]. You can also spot the pattern by looking at xors of such ranges, and it’s easy to explain as well.

Python

1
2
3
def missingNumber(self, nums):
n = len(nums)
return reduce(operator.xor, nums) ^ [n, 1, n+1, 0][n % 4]

Sum, without formula.

Java and C++:

1
2
3
4
int miss = 0, i = 0;
for (int num : nums)
miss += ++i - num;
return miss;

In Java I believe this is safe, overflow might happen but not cause a wrong result (because another overflow will fix it). In C++ I believe it’s probably safe in the same way, except that that behavior isn’t defined in the standard(s) but is a de-facto standard anyway. In any case, I could just use 64-bit ints again to be safe.

Set/array difference

Don’t know about Ruby’s runtime, might not be linear. Python’s sets are hash sets and the difference is linear time on average. Don’t know about its worst case, and apparently neither does the TimeComplexity page.

Python

1
2
def missingNumber(self, nums):
return (set(range(len(nums)+1)) - set(nums)).pop()

https://discuss.leetcode.com/topic/25998/clear-c-solution-that-can-avoid-overflow

Clear C++ solution that can avoid overflow

1
2
3
4
5
6
7
8
9
class Solution {
public:
int missingNumber(vector<int>& nums) {
int result = 0;
for (int i = 0; i < nums.size(); i++)
result ^= nums[i]^(i+1);
return result;
}
};

https://discuss.leetcode.com/topic/22366/simple-c-codes

Simple C++ codes

Using bit XOR operatons, just like the “find missing number (all elements except one occur twice, find the one that occurs once)” one

The reason I didn’t use sum[1..n] - sum(nums) is that calculating sum has potential to cause overflow. XOR bit operation is much safer.

1
2
3
4
5
6
7
8
9
class Solution {
public:
int missingNumber(vector<int>& nums) {
int missing =0;
for(int i=0; i<nums.size();++i)
missing ^= ((i+1)^nums[i]);
return missing;
}
};

https://discuss.leetcode.com/topic/42439/1-line-python-solution

1 line Python Solution

1
2
3
class Solution(object):
def missingNumber(self, nums):
return sum(range(len(nums)+1)) - sum(nums)
谢谢你,可爱的朋友。