題目
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?
Input:[4,3,2,7,8,2,3,1]
Output:[2,3]
分析
給定一個數(shù)組大小為n悄晃，數(shù)組中的數(shù)都在[1攀涵，n]范圍內(nèi)巾乳，有的數(shù)出現(xiàn)一次闷尿，有的出現(xiàn)兩次肛宋，找出所有出現(xiàn)兩次的數(shù)绣夺。
這道題要求O(n)時間復(fù)雜度和不用額外空間方援，其實是要利用數(shù)有范圍這個條件，[1,n]范圍正好可以對應(yīng)數(shù)組的下標式镐，如果出現(xiàn)了一次就對相應(yīng)下標的數(shù)據(jù)做一些不影響下次讀取的變化反镇，比如乘以-1，表示這個下標已經(jīng)出現(xiàn)過一次娘汞，下次再找到這個下標時發(fā)現(xiàn)這個數(shù)已經(jīng)是負數(shù)了歹茶，就表示是出現(xiàn)了兩次了。這種方法也可以得出出現(xiàn)多次的結(jié)果。
代碼
// when find a number i, flip the number at position i-1 to negative.
// if the number at position i-1 is already negative, i is the number that occurs twice.
public List<Integer> findDuplicates(int[] nums) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
int index = Math.abs(nums[i])-1;
if (nums[index] < 0)
res.add(index+1);
nums[index] = -nums[index];
}
return res;
}