网站模板手机,网站建设杭州,wordpress 定时发布 原理,关键词挖掘机爱站网题目#xff1a;找到所有数组中消失的数
题目详情#xff1a;
给你一个含 n 个整数的数组 nums #xff0c;其中 nums[i] 在区间 [1,n] 内。请你找出所以在 [1,n] 范围内但没有出现在 nums 中的数字#xff0c;并以数组的形式返回结果。
示例1#xff1a; 输入#xf…题目找到所有数组中消失的数
题目详情
给你一个含 n 个整数的数组 nums 其中 nums[i] 在区间 [1,n] 内。请你找出所以在 [1,n] 范围内但没有出现在 nums 中的数字并以数组的形式返回结果。
示例1 输入nums [ 43278231 ] 输出[ 56 ] 示例2 输入nums [ 11 ] 输出[ 2 ] 提示 nnums.length 1n105 1nums[i]n 解法一非原地修改法
解题思路
由题可得给定的数组都是在 [1, n] 范围内的数字,由此我们可以定义一个数组 arr 将 [1, n] 按顺序存起来此时无论什么数它所对应的下标都是本身减一
然后我们就想啊arr 的范围大小是包含于 nums 的而且 nums 里的整数在 arr 里对应的整数的下标都是其整数减一所以我们可以做标记来解决本题
遍历 nums 数组arr 中凡是在 nums 中出现过的整数都做标记-----记为0最后 arr 数组中不为0的数字就是消失的数字 思路实现
定义数组 arr 并赋值 int i0;int arr[100000]{0};for(i0;inumsSize;i){arr[i]i1;}
然后遍历 nums 数组找到 arr 中与之相对应的数的下标并将此下标处的数记为0比如nums[2]4则 arr 中对应 4 的下标为 nums[2] -13然后arr[nums[2] -1]0 for(i0;inumsSize;i){arr[nums[i]-1]0;}
创建一个动态内存变量 ret 用来存放消失的数字
遍历 arr 数组不为0的就是消失的数字并存放在 ret 中 int* ret(int*)malloc(4*numsSize);int k0;for(i0;inumsSize;i){if(arr[i]0){ret[k]arr[i];}}
此时 ret 中存放的数字就是消失的数字了返回 ret 即可
源代码
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){int* ret(int*)malloc(4*numsSize);int i0;int arr[100000]{0};for(i0;inumsSize;i){arr[i]i1;}for(i0;inumsSize;i){arr[nums[i]-1]0;}int k0;for(i0;inumsSize;i){if(arr[i]0){ret[k]arr[i];}}* returnSizek;return ret;
} 解法二原地修改法
解题思路
其实跟解法一有异曲同工之妙就是在解法一的基础上不使用 arr 数组自身解决一样的意思的解法一它后面侧重判断的点是 arr 的数值而我们解法二是原地修改侧重的是下标的数值具体如何听博主慢慢分晓
在数组 nums 中有着 n 个数字数字之间可能会重复一旦重复就会产生消失的数字此时我们将数组 nums 的数值与下标分离开来然后遍历 nums 然后将下标为 nums[i]-1的值加上 n 如果 nums[i]-1大于 n需要对其取模来还原出他本来的值
然后在创建动态内存变量 ret 来存储消失的数字遍历数组 nums 如果数字不大于n则此下标加一就是消失的数字的
思路实现
遍历数组 nums 将下标为 nums[i]-1的值加上 n如果此值大于 n 需要对其取模来还原即将下标为nums[i]-1)%n 的值加上 n int i0;for(i0;inumsSize;i){nums[(nums[i]-1)%numsSize]numsSize;}
创建一个动态内存变量 ret 用来存放消失的数字
遍历 nums 数组不大于 n 的数字的下标加一就是消失的数字 int* ret(int*)malloc(4*numsSize);int i0;int k0;for(i0;inumsSize;i){if(nums[i]numsSize){ret[k]i1;}}
此时 ret 中存放的数字就是消失的数字了返回 ret 即可
源代码
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize){int* ret(int*)malloc(4*numsSize);int i0;for(i0;inumsSize;i){nums[(nums[i]-1)%numsSize]numsSize;}int k0;for(i0;inumsSize;i){if(nums[i]numsSize){ret[k]i1;}}* returnSizek;return ret;
}
以上就是本题的两种解法其实都不算很复杂就是得画图得想到这里如果现在还不具备此思维也不要慌张正常现象而已多刷题锻炼思维即可
如有不足之处欢迎来补充交流
完结。。。
