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]return2.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
方法
對于0-n個數(shù)，它們的和sum是確定的瘸右，那么用sum減去給定n個數(shù)的和就求出了missing的那個數(shù)
c代碼
#include <assert.h>
int missingNumber(int* nums, int numsSize) {
int expectedSum = (1+numsSize)*numsSize/2;
int i = 0;
int sum = 0;
for(i = 0; i < numsSize; i++) {
sum += nums[i];
}
return expectedSum - sum;
}
int main() {
int nums[3] = {0, 1, 3};
assert(missingNumber(nums, 3) == 2);
return 0;
}
