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;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/6736.html
標籤：其他