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]
题目标签：Array
题目给了我们一个nums array，其中有一些数字出现两次，剩下的都只出现一次，让我们把重复两次的都找出来。
因为这道题目没有规定我们不能改动 array，所以可以把array 里的 num 和 在 nums[ num - 1 ] 做一对一的映射，每次遇到一个num， 把对应位置上的 num 改成 -num 标记。如果遇到一个重复项，那么肯定已经有同样的数字来标记过了。
Java Solution:
Runtime beats 85.92%
完成日期：09/19/2017
关键词：Array
关键点：把num 和 nums[num - 1] 做1对1的映射
class Solution
{
public List<Integer> findDuplicates(int[] nums)
{
List<Integer> duplicates = new ArrayList<>(); for(int num: nums)
{
int absNum = Math.abs(num); if(nums[absNum - 1] < 0) // if the number at position num - 1 is already negative
duplicates.add(absNum); // num is duplicate
else
nums[absNum - 1] *= -1;
} return duplicates;
}
}
参考资料：
https://discuss.leetcode.com/topic/64735/java-simple-solution
LeetCode 题目列表 - LeetCode Questions List