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]
思路：
1.1 Python中有個collections模塊诅迷，它提供了個類Counter嵌戈，用來跟蹤值出現(xiàn)了多少次摩钙。注意key的出現(xiàn)順序是根據(jù)計數(shù)的從大到小涌献。它的一個方法most_common(n)返回一個list, list中包含Counter對象中出現(xiàn)最多前n個元素凯沪。
1.2 heapq模塊有兩個函數(shù)：nlargest() 和 nsmallest() 可以從一個集合中獲取最大或最小的N個元素列表浅悉。heapq.nlargest (n, heap) #查詢堆中的最大元素辅肾，n表示查詢元素個數(shù)
1.3 使用字典锻拘，依次查看數(shù)組中的元素绪杏，如果在字典中下愈，則放入另外用來統(tǒng)計的list
class Solution(object):
def findDuplicates(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
return [no for no, count in collections.Counter(nums).items() if count > 1]
Java思路：（我還沒想明白:(）
// 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.
//The concept here is to negate each number's index as the input is 1 <= a[i] <= n (n = size of array).
// Once a value is negated, if it requires to be negated again then it is a duplicate.
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(Math.abs(index + 1));
nums[index] = -nums[index];
}
return res;
}
