赤城县城乡建设局网站,深圳网络营销和推广渠道,洛阳洛龙区网站建设,如何创建自己的博客网站题目#xff1a;力扣-448
给你一个含 n 个整数的数组 nums #xff0c;其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字#xff0c;并以数组的形式返回结果。
把数组中存在[1…n]的元素放其元素值-1的位置上#xff0c;第一个fo…题目力扣-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)
