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]
根据题目的条件: 只有充分挖掘利用才行啊
键值对!!!
将值作为键, 并置为负来判断是否遍历过
int index = Math.abs(nums[i])-1;
if (nums[index] < 0)
public class Solution {
// 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;
}
}
Find All Duplicates in an Array
原文：http://www.cnblogs.com/apanda009/p/7308184.html