编写将数组中重复元素（首次出现除外）替换为-1的函数

看起来你这段代码原本是在做删除重复元素并缩小数组长度的操作，但咱们的需求是把重复元素（除首次出现外）替换成-1，而不是删掉它们。我来帮你调整代码逻辑，完美实现需求～

问题分析 #

原代码通过移位元素、缩小数组长度来删除重复项，但我们需要保持数组原有长度不变，仅将非首次出现的重复值替换为-1（题目说明输入是正整数数组，所以-1不会和原元素冲突）。

基于原代码结构的修改方案 #

我们可以直接去掉原代码中的删除/移位逻辑，改为直接将重复元素设为-1，同时跳过已经被替换成-1的元素（避免误判）。以下是完整的C语言实现：

void replaceDuplicatesWithNegativeOne(int arr[], int size) {
    // 遍历数组中的每个元素作为基准
    for (int i = 0; i < size; i++) {
        // 如果当前元素已经是-1，跳过（是之前替换的重复项）
        if (arr[i] == -1) {
            continue;
        }
        // 检查后续所有元素是否重复
        for (int j = i + 1; j < size; j++) {
            if (arr[j] == arr[i]) {
                // 替换重复元素为-1，而非删除
                arr[j] = -1;
            }
        }
    }
}

逻辑说明 #

• 外层循环遍历每个元素，作为首次出现的基准项
• 内层循环检查后续元素，若和基准项重复则直接替换为-1
• 增加if (arr[i] == -1)的判断，跳过已经被标记的重复项，避免不必要的检查

用你的示例输入{1, 2, 5, 4, 2, 7, 1, 2}测试，处理后会得到{1,2,5,4,-1,7,-1,-1}，完全符合需求。

优化方案（时间复杂度O(n)） #

上面的嵌套循环时间复杂度是O(n²)，如果数组很大，效率会比较低。我们可以用哈希集合（或者布尔数组）记录已出现的元素，把时间复杂度降到O(n)：

#include <stdbool.h>
#include <stdlib.h>

void replaceDuplicatesWithNegativeOneOptimized(int arr[], int size) {
    if (size == 0) return;

    // 先找到数组中的最大值，确定布尔数组的大小
    int maxVal = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] > maxVal && arr[i] != -1) {
            maxVal = arr[i];
        }
    }

    // 分配内存创建标记数组，初始值全为false
    bool* seen = (bool*)calloc(maxVal + 1, sizeof(bool));
    if (seen == NULL) {
        // 处理内存分配失败的情况
        return;
    }

    for (int i = 0; i < size; i++) {
        if (arr[i] == -1) continue;
        
        if (seen[arr[i]]) {
            // 元素已出现过，替换为-1
            arr[i] = -1;
        } else {
            // 首次出现，标记为已见过
            seen[arr[i]] = true;
        }
    }

    // 释放内存
    free(seen);
}

逻辑说明 #

• 先用一次遍历找到数组中的最大值，创建对应大小的布尔数组seen，用来记录元素是否已出现
• 再次遍历数组，遇到首次出现的元素就标记为true，遇到重复元素就替换为-1
• 这种方法只需要两次线性遍历，效率更高，适合处理大规模数组

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