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;
// 计算出相对应的n
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++)
{
// 若存在 相对应的数值则 flag=1
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;
}