面试题 17.04. 消失的数字

消失的数字

1、题目详情

题目链接：leetcode消失的数字

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
注意：本题相对书上原题稍作改动

示例 1：

输入：[3,0,1]
输出：2
1
2

示例 2：

输入：[9,6,4,2,3,5,7,0,1]
输出：8
1
2

2、题目详解

（1）方法1

既然是从0到n的数字，我们可以直接对其进行排序。排序后，我们利用相邻元素的差为1，即可找到消失的数字。
这里的排序算法，我们选择的是归并排序，因为在排序算法中归并排序的时间复杂度是较低的。

#include
using namespace std;
#include

void merge(int* arr, int low, int mid, int high)
{
	int* b = new int[high - low + 1];
	int i = low, j = mid + 1, k = 0;
	while (i <= mid && j <= high)
	{
		if (arr[i] <= arr[j])b[k++] = arr[i++];
		else b[k++] = arr[j++];
	}
	while (i <= mid)b[k++] = arr[i++];
	while (j <= high)b[k++] = arr[j++];
	for (i = low, k = 0; i <= high; i++)
		arr[i] = b[k++];
	delete[] b;
}
void mergesort(int* A, int low, int high)
{
	
	if (low < high)
	{
		int mid = (low + high) / 2;
		mergesort(A, low, mid);
		mergesort(A, mid + 1, high);
		merge(A, low, mid, high);
	}
}
int main()
{
	int n;
	scanf("%d",&n);
	int arr[n];
	for (int i = 0; i < n; i++)
	{
		scanf("%d",arr+i);
	}
	mergesort(arr,0,n-1);
	for(int i=0;i<n-1;i++)
	{
		if(arr[i+1]-arr[i]==2)
		{
			printf("%d",arr[i+1]-1);
			return 0;
		}

	}
	printf("%d",n+1);
	
	
	return 0;
}
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

我们观察上面方法的空间复杂度和时间复杂度：

时间复杂度：O(nlogn)
空间复杂度：O(n)

这种方法的效率貌似并不高！并且不符合题目中时间复杂度为O(n)的要求！
（上面的方法行不通，这里就不把它写成接口函数的形式了。）

（2）方法2

我们可以将0-n的数字相加，然后减去输入的数字，最终得到的就是结果。

int missingNumber(int* nums, int numsSize)
{
    int sum1 = 0;
    int sum2 = 0;
    int temp = numsSize;
    int count = numsSize;
    while (temp--)
    {
        sum1 += count--;    
    }
    for (int i = 0; i < numsSize; i++)
    {
        sum2 += nums[i];
    }
    return (sum1 - sum2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度：O（N）
空间复杂度：O（1）

（3）方法3

我们开辟一个新的数组，然后将出现的数字记录到相应的位置，最后遍历数组，找到没有记录痕迹的数字。

int missingNumber(int* nums, int numsSize)
{
    int b[numsSize+1];
    for(int i=0;i<numsSize+1;i++)
    {
        b[i]=0;
    }
    for (int i = 0; i < numsSize; i++)
    {
        b[nums[i]] = 1;
    }
    for (int i = 0; i < numsSize+1; i++)
    {
        if (b[i] == 0)
        {
            return i;
        }
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度：O(N)
空间复杂度：O(N)

（4）方法4：

我们设定一个X=0，让X先跟[0,n]的所有值异或，X在跟数组中的每个值异或，最终X的值就是缺少的那个数字。
原理：
两个相同的数字异或结果是0。
0和任何数字异或都为数字本身。

int missingNumber(int* nums, int numsSize)
{
    int a = 0;
    int max = numsSize;
    while (max)
    {
        a ^= max--;
    }
    for (int i = 0; i < numsSize; i++)
    {
        a ^= nums[i];
    }
    return a;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度：O(N)
空间复杂度：O(1)

总结一下上述的方法：
方法1：时间复杂度：O(nlogn) 空间复杂度：O(n)
方法2：时间复杂度：O(N) 空间复杂度：O(1)
方法3：时间复杂度：O(N) 空间复杂度：O(N)
方法4：时间复杂度：O(N) 空间复杂度：O(1)

所以方法2和方法4是最优解。