寻找出现2次的数

寻找出现2次的数
给你一个数组，很大，但内存装得下。
已知数组中的数字是（1-n） n是最大数。每个数至少出现一次，但有其中的部分数出现了2次。数组没有排过序。

求出这些出现过两次的数，要求o(1)space,o(n)时间。
例子：

［3，2，2，1，3，4］  告诉你1-4和这个数组， 要求 返回［2，3］。
Add one more requirement: you can not change the original  num array

这题最容易想到的思路就是使用一个HashSet记录已经出现过1次的数字。不过既然数字的范围在1~n内且连续，所以完全可以用一个长度为n的Boolean数组代替之。如果要求O(1)空间，把这个Boolean数组挤进原数组前n个数的符号位中即可。如果要求最终结果是“不改变原数组中的值”，那再扫一遍把负数都反过来即可：

1. public static List<Integer> getDup(Integer[] num, int n) {
2.                 List<Integer> res = new ArrayList<Integer>();
3.                 for(int i = 0; i < num.length; ++i) {
4.                         int j = Math.abs(num[i]);   // 找到这个数字应该出现的位置
5.                         if (num[j-1] < 0) res.add(j);  // 如果这个数字已经出现过一次，则加入结果
6.                         else num[j-1] = -num[j-1];  // 否则，标记为“已出现”
7.                 }
8.                 for (int i = 0; i < n; ++i) { // 恢复原数组
9.                         if (num[i] < 0) num[i] = -num[i];
10.                 }
11.                 return res;
12.         }

If the problem has more requirements. That the input vector nums will be reused in the future. And we don't want change the nums. Do you have any other way to solve it?

面试官最后要希望我延用我之前bit的思想解这题，我只想出了一个最简单的想法，就是用n/32 个 32bit的数表示（这样并不是constant space），如此操作，每一位就是代表一个容器

那面试官的意思应该是用bitmap,因为之前已经告诉了范围是1-n, 每一位bit代表一个数字，每出现一次就xor, 最后是0的应该就是出现两次的数。
Read full article from 寻找出现2次的数