这个问题来自于微软的面试。
给定一个随机整数数组， 请用 C 语言编写一个算法，去除重复的数字并返回原始数组中的唯一数字。
例如，输入：{4, 8, 4, 1, 1, 2, 9} 输出：{4, 8, 1, 2, 9, ?, ?}
其中一个注意事项是，期望的算法不应该要求先对数组进行排序。当一个元素被移除后，后续的元素必须向前移位。无论如何，被移位的末尾元素的值都是可以忽略的。
更新：结果必须返回到原始数组中，不能使用帮助数据结构（例如哈希表）。然而，我猜想保持元素顺序并不是必需的。
更新2：对于那些想知道为什么有这些不切实际的限制的人，这是一个面试题，所有这些限制都是在思考过程中讨论的，以了解我如何提出不同的想法。
这里写的一些答案相当琐碎（O(n^2)或者O(NlogN)的排序和遍历），我认为这不是微软面试官所期望的。显然，任何超过O(n)的答案都不是他们想要的。
更新说明指出不应该使用任何辅助数据结构，因此任何有一个（哈希表、树、位数组或其他）的答案都不应该是有效的解决方案。
如果你可以分配额外的内存，那么Jeff B的答案可能是最简单的方法。
我对这类问题有一个很好的答案，但MAXINT需要受到数组大小的限制。（例如：大小为100的数组可能包含1到100之间的任何数字。删除重复项作为原始问题）
这个O(n)时间和O(1)内存的答案是：
// FLAG ALL DUPS IN THE ORIGIN ARRAY
int maxNumInArray = findMaxNumInArray(arr);
int dup = findMinNumInArray(arr) - 1;
for (int i=0; i < arrLength; ++i) {
int seekIndex = arr[i] % (maxNumInArray+1);
if (arr[seekIndex] > maxNumInArray)
arr[i] = dup; // invalidate index
else
arr[seekIndex] = arr[seekIndex] + maxNumInArray;
}
// REMOVE EMPTY SPACES
int i = 0;
int j = arrLength(arr)-1;
while (i<j) {
while (arr[i] != dup)
++i;
while (arr[j] == dup)
--j;
swap(arr[i], arr[j]);
}
如果您不知道边界，我的答案可能没有用，但您可以尝试并进行调整。 哦，还有这个特定的变体不能处理负数，但修复它并不是问题。
对于想要在C++中获得简单解决方案的人：
int* rmdup(int path[], int start, int end, int& newEnd) {
int ret[100];
newEnd = end;
int j = start;
for (int i = start; i < end; i++) {
if (path[i] == path[i+1]) {
newEnd--;
continue;
}
ret[j++] = path[i];
}
ret[j++] = path[end];
for(int i = start; i <= newEnd; i++)
path[i] = ret[i];
}
只需取一个变量x=arr[0]，通过遍历其余元素执行异或操作。如果一个元素重复出现，则x将变为零。
这样我们就知道该元素之前已经重复出现过了。这也只需要o(n)扫描原始数组中的所有元素。
Integer[] arrayInteger = {1,2,3,4,3,2,4,6,7,8,9,9,10};
Set set = new HashSet();
for(Integer i:arrayInteger)
set.add(i);
System.out.println(set);