算法 找到所有数组中消失的数字

---

前言

题目链接

给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。

---

一、思路

二、代码实现

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){

	if (numsSize == 0)
	{
		*returnSize = 0;
		return NULL;
	}

	int *ret = (int*)malloc(sizeof(int) * numsSize);

	int idx;
	/*
	数字范围 1~n 对应的数组下标为： 0 ~（n-1）,
	所以一个数组元素减去1，得到的数字应该是数组中的下标
	*/
	for (int iter = 0 ; iter < numsSize; iter++)
	{	
		//由于一个元素可能已经被修改过(+n)，所以需要取模还原
		idx = (nums[iter] - 1) % numsSize; //nums[iter] - 1;
		nums[idx] += numsSize; 
	}



	*returnSize = 0;
	for (int iter = 0 ; iter < numsSize; iter++)
	{	
		if (nums[iter] <= numsSize)
		{
			ret[*returnSize] = iter + 1;
			*returnSize = *returnSize + 1;
		}
	}

	return ret;
}
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