算法:从数组中删除重复整数的有效方法
我是在一次微软的采访中遇到这个问题的。
给定一个随机整数数组，用C语言编写一个算法，去掉重复的数字，并返回原始数组中的唯一数字。
例如输入：{4, 8, 4, 1, 1, 2, 9}输出：{4, 8, 1, 2, 9, ?, ?}
需要注意的是，预期的算法不应该要求首先对数组进行排序。当一个元素被移除时，下面的元素也必须前移。无论如何，数组尾部元素的值可以忽略不计。
更新：结果必须在原始数组中返回，并且不能使用辅助数据结构(例如哈希表)。然而，我猜顺序保留并不是必需的。
Update2:对于那些想知道为什么会有这些不切实际的约束的人来说，这是一个面试问题，所有这些约束都会在思考过程中讨论，看看我如何才能想出不同的想法。
回答 34
Stack Overflow用户
发布于 2009-10-07 17:39:06
这样如何：
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)或更小。
Stack Overflow用户
发布于 2009-10-07 18:00:28
我的女友建议的一个解决方案是合并排序的变体。唯一的修改是在合并步骤中，忽略重复的值。这个解决方案也是O(n log n)。在这种方法中，排序/重复删除被组合在一起。然而，我不确定这是否会有什么不同。
Stack Overflow用户
发布于 2009-10-07 19:27:25
我之前已经在SO上发布过一次，但我将在这里重现它，因为它非常酷。它使用散列，在适当的地方构建类似于散列集的东西。它保证在腋窝空间中是O(1) (递归是一个尾部调用)，并且通常是O(N)时间复杂度。算法如下：
散列取数组的第一个元素，这将是数组其余部分的散列，尽可能使每个元素都在与其sentinel.
- Reorder对应的位置上
- 。完成此步骤后，将发现重复项。将它们设置为等于sentinel。
- 将其索引等于散列的所有元素移到数组的开头。
- 将除数组的第一个元素之外的所有等于sentinel的元素移动到数组的末尾。
- 正确散列的元素和重复元素之间的剩余元素将是由于冲突而无法放入与其散列对应的索引中的元素。递归来处理这些元素。
如果在散列中没有病理情况，这可以被证明是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);
}https://stackoverflow.com/questions/1532819
复制相似问题
腾讯云开发者
