LeetCode-268. Missing Number
题目
Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.
Example 1:
1 2
| Input: [3,0,1] Output: 2
|
Example 2:
1 2
| Input: [9,6,4,2,3,5,7,0,1] Output: 8
|
Note:
1
| Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
|
分析
思路:
找出最大值,进行判断,看那一位数字缺少。
C语言代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| #include <stdio.h> int missingNumber(int* nums, int numsSize) { int n=numsSize+1;
for(int i=0;i<numsSize;i++) { if(n<nums[i]) { n=nums[i]; } }
for(int i=0;i<n;i++) { int flag=0; int j=0; for(;j<numsSize;j++) {
if(i==nums[j]) { flag=1; }
} if(flag==0&&j==numsSize) { return i; } } return 0; } int main() { int nums[]={0}; int numsSize= sizeof(nums)/ sizeof(int); printf("%d\n",missingNumber(nums,numsSize)); return 0; }
|