题目描述 LeetCode 268
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.
Example 1:
Input: [3,0,1]
Output: 2
Example 2:
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note:
Your algorithm should run in linear runtime complexity.
Could you implement it using only constant extra space complexity?
解题思路
- 题目中之处要用线性时间，也就是意味着不能用双层循环(比如，先排序，再找出缺失数字)。
- 本体思路是，因为原数组是
0 ~ n，中间缺失某个数字，则我们可以新创立一个temp数组(初始化为全为-1)，在原数组中有的数字上标记为1，则最后不为1的位置下标即为缺失数字 - 比如，先初始化
temp = [-1, -1, -1, -1]，输入原数组为 [3, 0, 1]，则temp = [1, 1, -1, 1 ]，可见temp数组在下标为2地方为-1，则原数组缺失为2
Code
# include<stdio.h>
int missingNumber(int* nums, int numsSize)
{
int i;
int k = 1;
int index;
int temp[100000];
// temp 数组初始化为 -1
for (i = 0; i <= numsSize; i ++)
{
temp[i] = -1;
}
// 开始遍历，在原数组有的数字下标处，在 temp 中相应位置标记为 1
for (i = 0; i < numsSize; i ++)
{
temp[nums[i]] = 1;
}
// 遍历，找到缺失数字 (位置不为1的下标，即为缺失数字)
for (i = 0; i <= numsSize; i ++)
{
if (k != temp[i])
{
index = i;
break;
}
}
return index;
}
int main()
{
//int a[10] = {9,6,4,2,3,5,7,0,1};
int a[10] = {1};
printf("%d\n\n",missingNumber(a, 1));
}
