- 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 | For example, |

Note:

Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

方法一：

位运算

美团面试遇到过

我的代码实现：

1 | class Solution { |

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

C++ solution using bit manipulation

1 | class Solution { |

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 | def missingNumber(self, nums): |

Java

1 | public int missingNumber(int[] nums) { |

C++

1 | int missingNumber(vector<int>& nums) { |

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 | def missingNumber(self, nums): |

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 | def missingNumber(self, nums): |

Sum, without formula.

Java and C++:

1 | int miss = 0, i = 0; |

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 | def missingNumber(self, nums): |

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

Clear C++ solution that can avoid overflow

1 | class Solution { |

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 | class Solution { |

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

1 line Python Solution

1 | class Solution(object): |