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?
对于给定的N个数，1<=a[i]<=N，可以使用基准排序，注意基准排序一般是线性时间，因为他不是基于数与数之间的比较的，数与数之间的比较的最佳时间是NLOGN。
因为是基排，所以我们使用数作为index去访问元素，如何可以做到标记已经访问的索引上的元素而不对后面的访问有影响呢？
一个可选的方案是对索引上的数置负，这样我们通过取反的方式，任然可以访问到nums[i]对应的索引上去。
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> result = new ArrayList<Integer>();
for(int i = 0 ;i<nums.length;i++)
{
int index = nums[i]<0?-nums[i]-1:nums[i]-1;
if(nums[index]<0)
result.add(index+1);
else
nums[index]=-nums[index];
}
return result;
}
}
