Find All Duplicates in an Array (M)
题目
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
Could you do it without extra space and in O(n) runtime?
Example:
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]
题意
给定一个长度为n的数组，其中元素的值域为1-n，求重复元素的集合，要求时间复杂度为(O(N))，空间复杂度为(O(1))。
思路
第一次遍历，重排元素使得尽可能满足(nums[i]=i+1)；第二次遍历，找到左右不满足(nums[i]=i+1)的元素，这些就是重复元素。
代码实现
Java
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> list = new ArrayList<>();
int i = 0;
while (i < nums.length) {
int j = nums[i] - 1;
if (nums[i] != nums[j]) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
} else {
i++;
}
}
i = 0;
while (i < nums.length) {
if (nums[i] != i + 1) {
list.add(nums[i]);
}
i++;
}
return list;
}
}
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
