首页 > 代码库 > 442. Find All Duplicates in an Array
442. Find All Duplicates in an Array
题目描述 442. Find All Duplicates in an Array
题目分析
遍历数组，将每次取出的值放入到正确的位置上，如nums[0]的值为4，则将4放入到nums[3]中（交换值方式）。
如果正确的位置已经有正确的值（nums[index]==index+1)，则不用处理。
如此，将不断地将值放入到正确的位置。而放不进去的值则为重复的值。
补充：可以使用LeetCode 448的思路，遍历数组，每取一值，index=nums[index]走一遍并一路做好标记，如果成环，则说明有重复值，但这样每次走一遍，都需要先清除标记在做好标记，就很繁琐了。另一方面时间复杂度也比较大了。
题目代码
public class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> list=new ArrayList<Integer>();
if(nums==null || nums.length==0 || nums.length==1) return list;
int index=0,temp,t;
while(index<nums.length){
temp=nums[index]-1;
if(nums[temp]!=temp+1){ //正确的位置上未放有正确的值
t=nums[temp];
nums[temp]=nums[index];
nums[index]=t;
}else
index++;
}
index=0;
while(index<nums.length){
if(nums[index]!=index+1) list.add(nums[index]);
index++;
}
return list;
}
}
442. Find All Duplicates in an Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。