重复移除

Question

老实说，这是个hw问题。

问题的全部内容：

在一维数组中用C++/Java在O(n)时间复杂度上实现重复删除算法，不需要额外的空间。例如，如果输入数组是{3，5，5，3，7，8，8，8，9}，那么输出应该是{3,5,7,8,9}。

我想了很久了，还没能解决这个问题。

我的想法：

1. 如果对数组进行排序，我可以删除O(n)中的重复项。但是我所知道的最快的排序算法具有O(n*log(n))的复杂性。
2. 在O(n)中排序的一种算法是bin或桶排序。这里的问题是，如果不使用额外的空间，就无法实现它。
3. 我想知道这是否有可能。

我做了一点研究，没有发现什么新的东西。

谢谢你的帮助。

如果不是因为明天的考试，我会给它更多的时间。

Answer 1

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

它运行于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;
}

N.B.#1:排序前倒置符号位的是正数大于负数所必需的，因为基数排序只对无符号值进行操作。

N.B.#2:，这只是一个粗略的例子，从来没有经过过真正的测试。

N.B.#3:哦，哇，这真的比qsort()快！

N.B.#4:，现在有s a non-recursive version of the sorting function; the usage is pretty much the same, save for the lack ofnbit`：

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);
}

Answer 2

假设ar[i]=j，检查ar[j]是否为负值，如果负删除ar[i] else将元素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
       }
    }