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?
C Solution 1:
int missingNumber(int* nums, int numsSize) {
int sum = 0;
int i;
for (i = 0; i < numsSize; i++) sum += nums[i];
return numsSize * (numsSize + 1) / 2 - sum;
}
C Solution 2:
int missingNumber(int* nums, int numsSize) {
int res = 0;
int i;
for (i = numsSize; i > 0; i--) {
res += i - nums[i - 1];
}
return res;
}
C Solution 3:
int missingNumber(int* nums, int numsSize) {
int res = numsSize;
int i;
for (i = 0; i < numsSize; i++) {
res ^= i ^ nums[i];
}
return res;
}
Python Solution:
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return (len(nums) * (len(nums) + 1) // 2) - sum(nums)
Summary:
- Be careful about overflow.
- Solution 3 is so beautiful.
- If the array is sorted, binary search is also a good choice.
LeetCode: 268. Missing Number
近期评论