网站建设的软件是哪个,品牌推广策略包括哪些内容,怎么扫码进入公众号,wordpress cdn注意事项原题链接#xff1a;数组中重复的数字
一、描述#xff1a;
在一个长度为 n 的数组 nums 里的所有数字都在 0#xff5e;n-1 的范围内。数组中某些数字是重复的#xff0c;但不知道有几个数字重复了#xff0c;也不知道每个数字重复了几次。请找出数组中任意一个重复的数…原题链接数组中重复的数字
一、描述
在一个长度为 n 的数组 nums 里的所有数字都在 0n-1 的范围内。数组中某些数字是重复的但不知道有几个数字重复了也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
二、样例
输入 [2, 3, 1, 0, 2, 5, 3] 输出 2 或 3
三、数据范围
2 n 100000
四、题解
1. 利用下标索引
即通过创建额外的数组空间用来记录各个数出现的次数具体实现方法是 1创建数组并将数组元素初始化为0 2遍历原数组以出现的数作为用于计数的数组的下标该下标所对应的计数数组中的元素 3计数数组中的元素若大于1则该元素所对应的下标就是原数组中那个重复的数字。 以样例为例 设计数数组为count[100001]则遍历原数组后可得到
count[0] 1;
count[1] 1;
count[2] 2;
count[3] 2;
count[5] 1;故2或3就是原数组中重复的数
完整代码
int findRepeatNumber(int* nums, int numsSize)
{int hash[100001] {0};int i 0;for(i 0; i numsSize; i){if(hash[nums[i]] 1)return nums[i];}return 0;
}复杂度分析 使用了额外的空间空间复杂度O(n) 遍历整个数组时间复杂度O(n)。
2. 原地置换重点学习
顾名思义算法的主要思想就是在原数组的基础上根据不同索引值进行数据的置换然后根据置换的结果就可以判断出那个重复的数下面详细介绍。 介绍之前先总结列出文中相关句段所对应的代码段可能会便于理解一些 设循环遍量为 i 则 当前元素或者说以 i 为下标索引得到当前元素表示为nums[i] 以循环变量 i 作为直接索引得到当前元素表示为i nums[i] 以当前元素本身 作为数组下标索引得到当前元素表示为: nums[nums[i]] nums[i] 这里再规定一下 “正确的位置” 的含义以便说明 “正确的位置” 代表该元素正好就是以该元素本身为数组下标索引所得的元素。如数组arr[5] {0, 2, 1, 3, 6}其中的元素0与元素3就处于 “正确的位置” 因为arr[0] 0arr[3] 3。
1算法思想遍历数组每遇到一个元素就检查该元素是否位于正确的位置上:
先以循环变量 i 作为直接索引进行检查即if(i nums[i])若符合条件则说明此时元素恰好位于正确的位置上原来在数组中就处于正确位置或交换后处于正确位置那么就执行i跳过而检查下一个元素再以该元素本身作为下标索引进行检查即if(nums[nums[i]] nums[i])若符合条件则说明此元素在之前已经出现过出现时的位置要么恰好是正确的位置要么是经过交换来到了正确的位置因此该元素就为重复元素若都不符合两种检查方式的条件则说明元素不在正确的位置上那么需与相对当前元素来说的正确位置上的元素进行交换从而让该元素元素处于正确位置但需要注意的是交换可以让当前元素处于正确的位置上但不能保证被交换的元素处于正确的位置上所以在执行完交换后i不进行直到使两个交换的元素都处于正确的位置上后才由条件if(i nums[i])来控制i的。后面有例
由如上描述可知符合第一种情况的一定符合第二种情况即若有i nums[i]则必有i nums[i] nums[nums[i]]反之则不一定成立这个不一定成立的情况也正是重复元素的情况即有 nums[i] nums[nums[i]]但同时i nums[i]
总结来说就是利用原地置换处理的数组对于数组中的不重复的元素必有i nums[i] 当不满足这个条件且满足 nums[i] nums[nums[i]]条件时nums[i]就是重复的元素
2样例说明对于数组 [2, 3, 1, 0, 2, 5, 3]原地置换的过程如下
当i 0时当前元素nums[i] 2, 元素 2 不在正确的位置上且以该元素本身为下标索引找到的元素 1 不等于当前元素所以将其与以2为下标的数组元素进行交换交换结果为 [1, 3, 2, 0, 2, 5, 3]交换完后发现当前元素nums[i] 1元素 1 不在正确的位置上且以该元素本身为下标索引找到的元素 3 不等于当前元素执行交换交换结果为:[3, 1, 2, 0, 2, 5, 3]交换完后发现当前元素nums[i] 3元素 3 不在正确的位置上且以该元素本身为下标索引找到的元素 0 不等于当前元素执行交换交换结果为:[0, 1, 2, 3, 2, 5, 3]交换完后发现当前元素位于正确位置i跳过进行下一个数的检查由此i一直到4当i 4时当前元素nums[i] 2不在正确的位置上但以该元素本身为下标索引能到的元素 2 等于当前元素说明当前元素为重复元素返回当前元素 23形象理解: 此形象理解来源于原题题解下的评论这里转述一下供大家参考: 这个原地交换法就相当于分配工作每个索引代表一个工作岗位每个岗位必须专业对口即0索引必须是0元素的“专业人才”才能上岗。而我们的目的就是通过专业对口的方式找出溢出的人才。我们先从0索引岗位开始遍历首先我们看0索引岗位是不是已经专业对口了如果已经专业对口即nums[0]0那我们就跳过0岗位看1岗位。如果0索引没有专业对口那么我们看现在0索引上的人才调整到他对应的岗位上比如num[0]2那我们就把2这个元素挪到他对应的岗位num[2]上这个时候有两种情况:1、num[2]岗位上已经有专业对口的人才了既num[2]2这就说明刚刚那个在num[0]上的2是溢出的人才我们直接将其返回即可。2、num[2]上的不是专业对口的人才那我们将num[0]上的元素和num[2]上的元素交换这样num[2]就找到专业对口的人才了。之后重复这个过程直到帮num[0]找到专业对口的人才然后以此类推帮num[1]找人才、帮num[2]找人才直到找到溢出的人才。 4算法实现注意事项
检查的次序问题如上所述应先检查if(i nums[i])再检查if(nums[nums[i]] nums[i])交换注意问题这里用一个错误的代码作为例子请看 tmp nums[i];nums[i] nums[nums[i]];nums[nums[i]] tmp;这样的交换存在问题在执行完第二句语句时nums[i]的值已被改为nums[nums[i]]故在第三句语句用nums[i]来作为数组下标索引时就达不到我们预期的效果最后一句语句我们想的把nums[i]的值赋给nums[nums[i]]而如上代码相当于是把nums[i]的值赋给了nums[nums[nums[i]]]这就出现问题了。 正确更改方式为把最后一句语句中的nums[i]作为下标索引改为tmp作为下标索引即nums[tmp] tmp;
复杂度分析 使用了常数复杂度的空间空间复杂度O(1) 遍历整个数组时间复杂度O(n)。
完整代码
int findRepeatNumber(int* nums, int numsSize)
{int i 0;int tmp 0;while(i numsSize){if(i nums[i]){i;continue;}if(nums[i] nums[nums[i]])return nums[i];if(i ! nums[i]){tmp nums[i];nums[i] nums[nums[i]];nums[tmp] tmp;//nums[i]的值已变故要用tmp索引}}return -1; //没有重复的元素返回-1
}看完觉得有觉得帮助的话不妨点赞收藏鼓励一下有疑问或看不懂的地方或有可优化的部分还恳请朋友们留个评论多多指点谢谢朋友们
