力扣【448-消失的数字】【数组-C语言】

题目：力扣-448

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

把数组中存在[1…n]的元素放其元素值-1的位置上，第一个for循环结束得到一个：nums[i] - 1 == i，（若数组中存在该元素）

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {for (int i = 0; i < numsSize; i++) {int t = nums[i];int k = nums[t - 1];while (t != k) {nums[t - 1] = t;t = k;k = nums[t - 1];}}*returnSize = 0;int *result = (int*)malloc(numsSize * sizeof(int));for (int i = 0; i < numsSize; i++) {if (nums[i] != (i + 1)) {result[(*returnSize)++] = i + 1;}}return result;
}

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

优化程序
每遍历一个元素t，就把nums[t-1]处的元素值加上n，直到for循环结束，使nums数组中存在[1…n]范围内的数字都大于n，第二个for循环遍历nums数组，把其中大于n的数字，加入数组result中。

int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {for (int i = 0; i < numsSize; i++) {int t = (nums[i] - 1) % numsSize;nums[t] += numsSize;}int* result = malloc(sizeof(int) * numsSize);*returnSize = 0;for (int i = 0; i < numsSize; i++) {if (nums[i] <= numsSize) {result[(*returnSize)++] = i + 1;}}return result;
}

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