-
Notifications
You must be signed in to change notification settings - Fork 1
/
268. Missing Number
57 lines (52 loc) · 1.93 KB
/
268. Missing Number
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/*
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.
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?
*/
//思路:先写一个数组,给他赋值,然后将nums排序,之后一一对比,如果有缺少的数,就输出;没有的话就输出下一个。
// 26ms 4.6%
int missingNumber(int* nums, int numsSize) {
int num[numsSize],i;
quicksort(nums,0,numsSize-1);//对给定的数组排序
for(i=0;i<numsSize;i++)//对于新数组赋值
num[i] = i;
for(i=0;i<numsSize;i++)//对比两个数组数值
if(num[i] != nums[i])
return num[i];
if(i == numsSize )//如果没有缺失返回下一个数
return i;
return;
}
void quicksort(int* nums,int left,int right)
{
int i,j,t,temp;
if(left>right)
return;
temp=nums[left]; //temp中存的就是基准数
i=left;
j=right;
while(i!=j)
{
//顺序很重要,要先从右边开始找
while(nums[j]>=temp && i<j)
j--;
//再找右边的
while(nums[i]<=temp && i<j)
i++;
//交换两个数在数组中的位置
if(i<j)
{
t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
//最终将基准数归位
nums[left] = nums[i];
nums[i] = temp;
quicksort(nums,left,i-1);//继续处理左边的,这里是一个递归的过程
quicksort(nums,i+1,right);//继续处理右边的 ,这里是一个递归的过程
}