重复项去除

Question

重复项去除

arraysalgorithmduplicates

4

让我们坦诚，这是一道作业题。

完整的问题如下：

使用C++/Java在O(n)时间复杂度内实现一维数组的重复项删除算法，且不使用额外的空间。例如，如果输入数组为{3,5,5,3,7,8,5,8,9,9}，则输出应为{3,5,7,8,9}。

我已经思考了相当长的时间，但还没有解决它。

我的想法：

1. 如果数组已排序，则可以在O(n)中去除重复项。但我所知道的最快排序算法的复杂度为O(n*log(n))。

2. 一种在O(n)中进行排序的算法是二进制或桶排序。但问题在于它不能在不使用额外空间的情况下实现。

3. 我不知道是否有可能。

我已经做了一些研究，但没有发现任何新的东西。

感谢任何帮助。

附言：如果不是明天的考试，我会给它更多的时间。

- frederick99

2

一个哈希表可以在O(1)时间内告诉你它的集合中是否存在一个元素。这应该能指引你朝正确的方向前进。 - Rob

2

然而，哈希表需要空间，并且它说“不使用额外空间”。 - Martin Liversage

@MartinLiversage 好的，你说得对，我漏掉了这一部分。 - Rob

我想过一些 O(n) 的解决方案，比如使用 bool 数组，但那会占用空间。我真的需要它完成。 - frederick99

1

要求在空间复杂度上为O(1)，时间复杂度上为O(n)是非常困难的，甚至可能不可能。然而，我发现了一个适用于整数的算法，并声称在这些限制范围内（至少在正常情况下）有效。它使用递归，但可以使用尾调用来避免额外的内存需求。 - Martin Liversage

显示剩余3条评论

2个回答

1

假设 ar[i]=j，检查 ar[j] 是否为负数，如果是，则删除 ar[i]，否则将元素 ar[j] 替换为 -ar[j]。

注意：这仅适用于所有元素均为正数且元素位于 0<=elements<array_size 范围内。

    for(int i = 0; i < ar.length; i++) {
       int elem1 = ar[i];
       int elem2 = ar[Math.abs(elem1)];
       if(elem2 >= 0) {
           ar[Math.abs(elem1)] = -elem2;
       }
       else {
           //elem1 already exists in an array. remove elem1 or copy distinct elements to another array
       }
    }

- Nikita Mantri

它引发了 java.lang.ArrayIndexOutOfBoundsException。 - frederick99

你能包含你想要做的事情吗？ - frederick99

如果元素不在数组大小的范围内，就会出现ArrayIndexOutOfBoundException异常，正如我之前所提到的。 - Nikita Mantri

不，这是因为你将元素变成了负数，并且在代码中没有处理它。我想知道你是否能修改你的代码并使其正常工作。 - frederick99

这是一个很棒的答案！ :D - frederick99

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hidefromkgb · Accepted Answer

这是确实可能的，只需使用原地基数排序即可。

它运行时间为O(kn)，其中k对于任何标准数字数据类型都是常数，并且需要O(1)额外空间。

以下是代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

/// in-place 32-bit recursive radix sort
void I32R(int32_t *data, uint32_t size, uint32_t nbit) {
    uint32_t dbgn = (uint32_t)-1, dend = size;

    while (++dbgn < dend)
        if (data[dbgn] & nbit)
            while (dbgn < --dend)
                if (~data[dend] & nbit) {
                    data[dbgn] ^= data[dend];
                    data[dend] ^= data[dbgn];
                    data[dbgn] ^= data[dend];
                    break;
                }
    if ((nbit >>= 1) && (dend > 1))
        I32R(data, dend, nbit);
    if (nbit && (size - dend > 1))
        I32R(data + dend, size - dend, nbit);
}

/// O_t(n) / O_s(1) duplicate remover
int32_t dups(int32_t *data, uint32_t size) {
    int32_t iter, *uniq = data;

    if (size < 2)
        return size;
    for (iter = 0; iter < size; iter++)
        data[iter] ^= (1 << 31);
    I32R(data, size, 1 << 31);
    data[0] ^= (1 << 31);
    for (iter = 1; iter < size; iter++)
        if (*uniq != (data[iter] ^= (1 << 31)))
            *++uniq = data[iter];
    return uniq - data + 1;
}

void parr(int32_t *data, uint32_t size) {
    for (; size; size--)
        printf("%4d%s", *data++, (size == 1)? "\n\n" : ", ");
}

int main() {
    int32_t iter, size, *data;

    data = malloc((size = 256) * sizeof(*data));
    for (iter = 0; iter < size; iter++)
        data[iter] = (int8_t)rand() & -3;
    parr(data, size);
    parr(data, dups(data, size));
    free(data);
    return 0;
}

注意1：在排序之前反转符号位对于使正数大于负数是必要的，因为基数排序仅对无符号值进行操作。

注意2：这只是一个粗略的示例，从未真正测试过。

注意3：哇，这实际上比qsort()更快！

注意4：现在有一个非递归版本的排序函数；用法几乎相同，除了没有nbit外：

void I32NR(int32_t *data, uint32_t size) {
    int32_t mask, head;
    struct {
        uint32_t init, size, nbit, edge;
    } heap[32];

    heap[0].nbit = 32;
    heap[0].size = size;
    heap[0].init = head = 0;
    do {
        size = heap[head].init - 1;
        mask = 1 << ((heap[head].nbit & 0x7F) - 1);
        heap[head].edge = heap[head].size;
        while (++size < heap[head].edge)
            if (data[size] & mask)
                while (size < --heap[head].edge)
                    if (~data[heap[head].edge] & mask) {
                        data[size] ^= data[heap[head].edge];
                        data[heap[head].edge] ^= data[size];
                        data[size] ^= data[heap[head].edge];
                        break;
                    }
        heap[head].nbit = ((heap[head].nbit & 0x7F) - 1)
                        |  (heap[head].nbit & 0x80);
        if ((heap[head].nbit & 0x7F) && (heap[head].edge > 1)) {
            heap[head + 1] = heap[head];
            heap[head + 1].size = heap[head].edge;
            heap[++head].nbit |= 0x80;
            continue;
        }
        do {
            if ((heap[head].nbit & 0x7F)
            &&  (heap[head].size - heap[head].edge > 1)) {
                heap[head + 1] = heap[head];
                heap[head + 1].init = heap[head].edge;
                heap[++head].nbit &= 0x7F;
                break;
            }
            while ((head >= 0) && !(heap[head--].nbit & 0x80));
        } while (head >= 0);
    } while (head >= 0);
}