求修正O(nlogn复杂度的数组重复元素移至末尾函数实现问题

实现一个函数，接收int类型数组及整数n（数组大小），检查数组中的重复元素并将其移至数组末尾（元素取值范围为-n到n），返回数组中唯一元素的数量。

示例：

• 原数组：7 1 3 7 1 6 5
• 处理后数组：7 1 3 6 5 7 1
• 唯一元素数量：5

int moveDuplicatesV1(int* arr, int n) {
    int* aux = (int*)calloc((2 * n) + 1, sizeof(int));
    assert(aux);
    int uniq = 0;
    int i;
    int last = -1;
    for (i = 0; i < n; i++) {
        aux[arr[i] + n]++;
        if (aux[arr[i] + n] == 1)
        {
            if (last != -1)
            {
                swap(arr + i, arr + last);
                i = last;
            }
            last = i + 1;
        }
        else
            uniq--;
        if (aux[arr[i]] != 1)
            uniq++;
    }
    return uniq;
}

当前实现输出不符合预期，代码如下：

int moveDuplicatesV2(int* arr, int n) {
int i = 0, j = 0, k = 0, uniq = 0, dubs = 0;;
int* temp = (int*)calloc(n,sizeof(int));
assert(temp);
for (j = 0; j < n; j++) {
    temp[j]=arr[j];
}
merge_sort(temp, 0, n - 1);
for (i = 0; i < n; i++) {
    int left = bin_search(temp[i], temp, n);
    int right = bin_search_last(temp[i], temp, n);
    if (left == -1 || right == -1) {
        uniq++;
    }
    else {
        dubs = bin_search_last(temp[i], arr, n);
        swap(dubs, arr[n-1]);
        uniq++;
    }

}
    return uniq;
}

int bin_search(int key, int* a, int n)
{
    int* low, * high, * mid;
    low = a;
    high = a + n - 1;
    while (low <= high)
    {
        mid = low + (high - low) / 2;
        if (key == *mid)
            return 1;
        else if (key < *mid)
            high = mid - 1;
        else
            low = mid + 1;
    }
    return 0;
}

int bin_search_last(int key, int* a, int n)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (key < a[mid])
            high = mid - 1;
        else
            if (key > a[mid])
                low = mid + 1;
            else
                if ((low == high) || (a[mid + 1] > key))
                    return mid;
                else
                    low = mid + 1;
    }
    return -1;
}

void swap(int* v, int* u)
{
    int temp;
    temp = *v;
    *v = *u;
    *u = temp;
}

void merge(int* a, int p, int q, int r)
{
    int i = p, j = q + 1, k = 0;
    int* temp = (int*)malloc((r - p + 1) * sizeof(int));
    assert(temp);
    while ((i <= q) && (j <= r))
        if (a[i] < a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    while (j <= r)
        temp[k++] = a[j++];
    while (i <= q)
        temp[k++] = a[i++];
    for (i = p, k = 0; i <= r; i++, k++)
        a[i] = temp[k];
    free(temp);
}

void merge_sort(int* a, int first, int last)
{
    int middle;
    if (first < last) {
        middle = (first + last) / 2;
        merge_sort(a, first, middle);
        merge_sort(a, middle + 1, last);
        merge(a, first, middle, last);
    }
}

核心问题分析 #

1. bin_search函数逻辑误用：该函数返回1表示元素存在，0表示不存在，但代码中拿返回值和-1比较，逻辑完全错误。
2. 遍历逻辑混乱：循环遍历整个数组n次，会重复处理同一元素的重复项，导致重复交换、计数错误。
3. 二分查找原数组无效：bin_search_last仅适用于有序数组，但原数组arr未排序，直接调用会返回错误索引。
4. swap参数类型不匹配：swap需要传入指针，但代码中传入的是索引值和数组元素，会引发内存访问错误。

修正后的moveDuplicatesV2实现 #

思路：先排序临时数组提取唯一元素，再遍历原数组将唯一元素保留在前半部分，重复元素移至后半部分，最后统计唯一元素数量。

int moveDuplicatesV2(int* arr, int n) {
    if (n <= 0) return 0;

    int* temp = (int*)calloc(n, sizeof(int));
    assert(temp);
    for (int j = 0; j < n; j++) {
        temp[j] = arr[j];
    }
    merge_sort(temp, 0, n - 1);

    // 从排序后的数组提取唯一元素并计数
    int unique_count = 0;
    int last_val = temp[0] - 1; // 初始化为不存在的值
    for (int i = 0; i < n; i++) {
        if (temp[i] != last_val) {
            last_val = temp[i];
            unique_count++;
        }
    }

    // 标记元素是否已被保留到前面
    int* seen = (int*)calloc(2 * n + 1, sizeof(int));
    assert(seen);
    int write_pos = 0;

    // 把首次出现的元素放到数组前半部分
    for (int i = 0; i < n; i++) {
        int idx = arr[i] + n;
        if (seen[idx] == 0) {
            seen[idx] = 1;
            arr[write_pos++] = arr[i];
        }
    }

    // 把重复元素放到数组后半部分
    for (int i = 0; i < n && write_pos < n; i++) {
        int idx = arr[i] + n;
        if (seen[idx] > 1) {
            arr[write_pos++] = arr[i];
        } else if (seen[idx] == 1) {
            seen[idx] = 2; // 标记已处理过首次出现的元素
        }
    }

    free(temp);
    free(seen);
    return unique_count;
}

辅助函数修正说明 #

bin_search函数逻辑本身没问题，但moveDuplicatesV2中不需要用到它；bin_search_last仅适用于有序数组，调用前需确保数组已排序。

内容的提问来源于stack exchange，提问作者MadneSs