標(biāo)簽（空格分隔）： 數(shù)組 leetcode 刷題
題目鏈接
給定一個(gè)數(shù)組多艇，1≤a[i]≤n（n =數(shù)組的大屑テ辍）嫩实，里面的值唯一或者只出現(xiàn)兩遍醉者。復(fù)雜度O(n),空間復(fù)雜度O(1).
注意是返回?cái)?shù)組中的重復(fù)值５痢！返回的是list撬即。
不利用額外的空間（但是可以新建一個(gè)list立磁。。）
Input:
[4,3,2,7,8,2,3,1]
Output:
[2,3]
Java版搞莺，44 ms 19％ 不是很好息罗，猜測(cè)是因?yàn)榕判蛄?而且沒有充分利用只重復(fù)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里最快和最好的解法：
這里的概念是當(dāng)輸入的value是1 <= a [i] <= n（n =數(shù)組的大胁挪住）時(shí)迈喉，按索引獲得的值作下一個(gè)索引。比如value 8出現(xiàn)2次温圆，第一次走的時(shí)候把nums[value]標(biāo)注為負(fù)挨摸，那么按照value來(lái)走到下一個(gè)的時(shí)候，會(huì)有2次走到nums[value]岁歉。一旦value為負(fù)數(shù)得运，那么它是重復(fù)的膝蜈。
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;
}
