标签（空格分隔）： 数组 leetcode 刷题
题目链接
给定一个数组，1≤a[i]≤n（n =数组的大小），里面的值唯一或者只出现两遍。复杂度O(n),空间复杂度O(1).
注意是返回数组中的重复值！！返回的是list。
不利用额外的空间（但是可以新建一个list。。）
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]
Java版，44 ms 19％ 不是很好，猜测是因为排序了,而且没有充分利用只重复2次的特性。
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> newList = new ArrayList<Integer>(); // creating a new List
if(nums.length == 0) return newList;
Arrays.sort(nums);//O(logn)
int point = 0;
int i = 1;
int len = nums.length;
while( i < len){
if( i < len && nums[i-1] == nums[i]){
newList.add(nums[i]);
}
i++;
}
return newList;
}
}
solution里最快和最好的解法：
这里的概念是当输入的value是1 <= a [i] <= n（n =数组的大小）时，按索引获得的值作下一个索引。比如value 8出现2次，第一次走的时候把nums[value]标注为负，那么按照value来走到下一个的时候，会有2次走到nums[value]。一旦value为负数，那么它是重复的。
List<Integer> newList = new ArrayList<Integer>();
// creating a new List
for(int i=0;i<nums.length;i++){
int index =Math.abs(nums[i]); // Taking the absolute value to find index
if(nums[index-1] >0){
nums[index-1] = - nums[index-1];
}else{
// If it is not greater than 0 (i.e) negative then the number is a duplicate
newList.add(index);
}
}
return newList;
}
