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