网站底部关键词内链,wordpress子目录和多域名,网站开发总结报告,一个做问卷调查的网站好442. 数组中重复的数据
给定一个整数数组 a#xff0c;其中1 ≤ a[i] ≤ n #xff08;n为数组长度#xff09;, 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗#xff1f;
示例其中1 ≤ a[i] ≤ n n为数组长度, 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。
你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗
示例输入:
[4,3,2,7,8,2,3,1]输出:
[2,3]解题思路
将nums[i]中的元素放入其对应的下标中因为1 ≤ a[i] ≤ n在没有出现重复的元素的情况下应该是每一个元素都可以放在其对应的下标中一旦出现重复的元素就说明了会出现两个元素放入一个下标的情况
代码
class Solution {void swap(int[]nums,int l,int r){int tnums[r];nums[r]nums[l];nums[l]t;}public ListInteger findDuplicates(int[] nums) {ListInteger resnew ArrayList();for(int i0;inums.length;i){while(nums[i]0nums[i]!i1){if(nums[nums[i]-1]nums[i]){res.add(nums[i]);nums[i]-1;break;} swap(nums,i,nums[i]-1);}}return res;}
}
