这个问题来自于微软的面试。
给定一个随机整数数组， 请用 C 语言编写一个算法，去除重复的数字并返回原始数组中的唯一数字。
例如，输入：{4, 8, 4, 1, 1, 2, 9} 输出：{4, 8, 1, 2, 9, ?, ?}
其中一个注意事项是，期望的算法不应该要求先对数组进行排序。当一个元素被移除后，后续的元素必须向前移位。无论如何，被移位的末尾元素的值都是可以忽略的。
更新：结果必须返回到原始数组中，不能使用帮助数据结构（例如哈希表）。然而，我猜想保持元素顺序并不是必需的。
更新2：对于那些想知道为什么有这些不切实际的限制的人，这是一个面试题，所有这些限制都是在思考过程中讨论的，以了解我如何提出不同的想法。
我的女友提出的解决方案是归并排序的一种变体。唯一的修改是在合并步骤中，忽略重复的值。这个解决方案同样是O(n log n)。在这种方法中，排序/去重复操作被结合在一起。然而，我不确定这是否有任何区别。
我之前曾在SO上发布过这个算法，但我会在这里再次重复一遍，因为它非常酷。它使用哈希技术，在原地构建类似哈希集合的东西。它保证在辅助空间（递归是尾调用）方面的复杂度为O(1)，通常时间复杂度为O(N)。该算法如下：
只要哈希没有病态情况，这可以被证明是O(N)：即使没有重复项，大约2/3的元素都会在每次递归中被消除。每个递归层是O(n)，其中小n是剩余的元素数量。唯一的问题在于，实际上，当有很少的重复项时，即存在大量冲突时，它比快速排序慢。但是，当存在大量重复项时，它非常快。
编辑：在当前的D实现中，hash_t是32位的。关于此算法的所有内容都假定在完整的32位空间中几乎没有或完全没有哈希冲突。在模数空间中可能经常发生碰撞。但是，这个假设对于任何大小合理的数据集来说，很可能是正确的。如果键小于或等于32位，则它可以是自己的哈希，这意味着在完整的32位空间中不可能出现冲突。如果它更大，你只需无法将足够多的键放入32位内存地址空间中，以免造成问题。我假设在D的64位实现中，hash_t将增加到64位，在那里数据集可以更大。此外，如果这曾经被证明是一个问题，可以在每个递归级别更改哈希函数。
以下是D编程语言中的一个实现：
void uniqueInPlace(T)(ref T[] dataIn) {
uniqueInPlaceImpl(dataIn, 0);
}
void uniqueInPlaceImpl(T)(ref T[] dataIn, size_t start) {
if(dataIn.length - start < 2)
return;
invariant T sentinel = dataIn[start];
T[] data = dataIn[start + 1..$];
static hash_t getHash(T elem) {
static if(is(T == uint) || is(T == int)) {
return cast(hash_t) elem;
} else static if(__traits(compiles, elem.toHash)) {
return elem.toHash;
} else {
static auto ti = typeid(typeof(elem));
return ti.getHash(&elem);
}
}
for(size_t index = 0; index < data.length;) {
if(data[index] == sentinel) {
index++;
continue;
}
auto hash = getHash(data[index]) % data.length;
if(index == hash) {
index++;
continue;
}
if(data[index] == data[hash]) {
data[index] = sentinel;
index++;
continue;
}
if(data[hash] == sentinel) {
swap(data[hash], data[index]);
index++;
continue;
}
auto hashHash = getHash(data[hash]) % data.length;
if(hashHash != hash) {
swap(data[index], data[hash]);
if(hash < index)
index++;
} else {
index++;
}
}
size_t swapPos = 0;
foreach(i; 0..data.length) {
if(data[i] != sentinel && i == getHash(data[i]) % data.length) {
swap(data[i], data[swapPos++]);
}
}
size_t sentinelPos = data.length;
for(size_t i = swapPos; i < sentinelPos;) {
if(data[i] == sentinel) {
swap(data[i], data[--sentinelPos]);
} else {
i++;
}
}
dataIn = dataIn[0..sentinelPos + start + 1];
uniqueInPlaceImpl(dataIn, start + swapPos + 1);
}
怎么样：
void rmdup(int *array, int length)
{
int *current , *end = array + length - 1;
for ( current = array + 1; array < end; array++, current = array + 1 )
{
while ( current <= end )
{
if ( *current == *array )
{
*current = *end--;
}
else
{
current++;
}
}
}
}
应该是 O(n^2) 或更低的时间复杂度。
另一种更高效的实现方法
int i, j;
/* new length of modified array */
int NewLength = 1;
for(i=1; i< Length; i++){
for(j=0; j< NewLength ; j++)
{
if(array[i] == array[j])
break;
}
/* if none of the values in index[0..j] of array is not same as array[i],
then copy the current value to corresponding new position in array */
if (j==NewLength )
array[NewLength++] = array[i];
}
如果您正在寻找更高级的O-符号，则使用O（nlogn）排序对数组进行排序，然后进行O（n）遍历可能是最佳选择。如果不进行排序，则需要O（n ^ 2）的时间复杂度。
编辑：如果只处理整数，则还可以使用基数排序以获得O（n）。
1. 使用 O(n log n) 的时间复杂度，在 O(1) 的额外空间内进行
这是可能的，例如：
我认为 ejel 的伙伴正确指出了最好的方法是使用原地归并排序和简化的归并步骤，并且如果您例如正在编写一个新的库函数以尽可能高效地处理此类输入而没有能力改进输入，则可能是问题的意图，并且在某些情况下，不使用哈希表进行此操作将非常有用。但是我没有实际检查过。
2. 使用 O(lots) 的额外空间，在 O(n) 的时间复杂度内进行
只有在满足几个可疑的假设的情况下才能起作用：
这是一个糟糕的答案，但是如果您有许多输入元素，但它们都是8位整数（甚至可能是16位整数），那么它可能是最佳方法。
3. O(little)-ish 额外空间，O(n)-ish 时间
与#2相同，但使用哈希表。
4. 清晰的方法
如果元素数量很少，则编写适当的算法没有用，如果其他代码编写和阅读速度更快，则不需要。
例如，遍历每个唯一元素的数组（即第一个元素，第二个元素（删除第一个的副本）等），移除所有相同的元素。O(1)额外空间，O(n^2)时间。
例如，使用库函数来完成此操作。效率取决于您能够轻松获取哪些函数。
基本实现非常简单。遍历所有元素，检查剩余元素中是否有重复项，并将其余元素移动到它们上面。
这种方法效率非常低下，你可以通过输出辅助数组或排序/二叉树来加快速度，但似乎不允许使用这些方法。
这个函数的返回值应该是唯一元素的数量，并且它们都存储在数组的前面。如果没有这个额外的信息，你甚至不知道是否有任何重复项。
外部循环的每次迭代处理数组中的一个元素。如果它是唯一的，它保留在数组的前面；如果是重复的，它将被数组中未处理的最后一个元素覆盖。这种解决方案的运行时间为O(n^2)。
#include <stdio.h>
#include <stdlib.h>
size_t rmdup(int *arr, size_t len)
{
size_t prev = 0;
size_t curr = 1;
size_t last = len - 1;
while (curr <= last) {
for (prev = 0; prev < curr && arr[curr] != arr[prev]; ++prev);
if (prev == curr) {
++curr;
} else {
arr[curr] = arr[last];
--last;
}
}
return curr;
}
void print_array(int *arr, size_t len)
{
printf("{");
size_t curr = 0;
for (curr = 0; curr < len; ++curr) {
if (curr > 0) printf(", ");
printf("%d", arr[curr]);
}
printf("}");
}
int main()
{
int arr[] = {4, 8, 4, 1, 1, 2, 9};
printf("Before: ");
size_t len = sizeof (arr) / sizeof (arr[0]);
print_array(arr, len);
len = rmdup(arr, len);
printf("\nAfter: ");
print_array(arr, len);
printf("\n");
return 0;
}
如果您愿意牺牲内存，可以在单次遍历中完成此操作。您可以在哈希/关联数组中简单地计算您是否已经看到了一个整数。如果您已经看到了一个数字，请在进行操作时将其删除，或者更好的方法是将您没有看到的数字移动到一个新数组中，避免对原始数组进行任何移动。
在 Perl 中：
foreach $i (@myary) {
if(!defined $seen{$i}) {
$seen{$i} = 1;
push @newary, $i;
}
}
std :: sort 后跟调用std :: unique 将为您提供答案。排序的时间复杂度为O（N log N），唯一遍历的时间复杂度为O（N）。如果无法使用C ++，则这些算法也可以在C中编写。