出现多次的数组元素？

《出现多次的数组元素？——C/C++中高效查找重复元素的算法实践》

在计算机编程中，处理数组数据时常常需要识别重复元素。无论是用于数据清洗、统计分析还是算法优化，快速定位重复值都是基础且重要的操作。本文将深入探讨C/C++中查找数组中重复元素的多种方法，从暴力解法到哈希表优化，从排序预处理到位运算技巧，结合时间复杂度分析与实际代码实现，为开发者提供完整的解决方案。

一、问题定义与基础场景

给定一个包含n个元素的数组，如何高效找出所有出现次数超过1次的元素？例如，数组[1, 2, 3, 2, 4, 3, 5]中，重复元素为2和3。根据输入规模的不同，解决方案可分为小规模数据（n

二、基础解法：暴力枚举

最直观的方法是双重循环遍历数组，外层循环固定当前元素，内层循环检查后续元素是否相同。该方法时间复杂度为O(n²)，空间复杂度为O(1)，适用于极小规模数据。

#include 
void findDuplicatesBruteForce(int arr[], int n) {
    printf("重复元素(暴力法): ");
    for (int i = 0; i 

输出结果：重复元素(暴力法): 2 3

缺陷：当n=10⁴时，比较次数达5×10⁷次，性能极差。

三、排序预处理法

通过先对数组排序（O(n log n)），使重复元素相邻，再线性扫描（O(n)）即可。总时间复杂度O(n log n)，空间复杂度O(1)（若使用原地排序）。

#include 
#include 
int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}
void findDuplicatesSort(int arr[], int n) {
    qsort(arr, n, sizeof(int), compare);
    printf("重复元素(排序法): ");
    for (int i = 0; i 

输出结果：重复元素(排序法): 2 3

优势：适合链表等不易随机访问的数据结构，且可扩展为统计重复次数。

四、哈希表优化法

利用哈希表记录元素出现次数，实现O(n)时间复杂度和O(n)空间复杂度。C++中可使用unordered_map，C语言需手动实现链表法或开放寻址法哈希表。

#include 
#include 
#define TABLE_SIZE 100
typedef struct Node {
    int key;
    int count;
    struct Node *next;
} Node;
Node *hashTable[TABLE_SIZE] = {NULL};
unsigned int hash(int key) {
    return abs(key) % TABLE_SIZE;
}
void insert(int key) {
    unsigned int index = hash(key);
    Node *current = hashTable[index];
    while (current != NULL) {
        if (current->key == key) {
            current->count++;
            return;
        }
        current = current->next;
    }
    Node *newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->count = 1;
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}
void findDuplicatesHash(int arr[], int n) {
    for (int i = 0; i count > 1) {
                printf("%d ", current->key);
            }
            current = current->next;
        }
    }
    printf("\n");
    // 释放内存
    for (int i = 0; i next;
            free(temp);
        }
    }
}
int main() {
    int arr[] = {7, 3, 2, 7, 4, 3, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    findDuplicatesHash(arr, n);
    return 0;
}

输出结果：重复元素(哈希法): 3 7

C++简化版（使用unordered_map）：

#include 
#include 
#include 
using namespace std;
vector findDuplicatesCPP(int arr[], int n) {
    unordered_map freq;
    vector duplicates;
    for (int i = 0; i  1) duplicates.push_back(pair.first);
    }
    return duplicates;
}
int main() {
    int arr[] = {1, 2, 3, 2, 4, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    vector res = findDuplicatesCPP(arr, n);
    cout 

五、位运算技巧（特定场景）

当数组元素为0-31的整数时，可用整型变量的位表示存在性。例如，使用一个int的32位记录数字出现情况。

#include 
void findDuplicatesBitwise(int arr[], int n) {
    int bitSet = 0;
    printf("重复元素(位运算法): ");
    for (int i = 0; i 

输出结果：重复元素(位运算法): 2 3 1

限制：仅适用于小范围非负整数，且无法统计重复次数。

六、进阶优化：空间换时间

若允许修改原数组，可将元素作为索引标记。例如，对正整数数组，将对应索引处的值取负表示已访问。

#include 
void findDuplicatesInPlace(int arr[], int n) {
    printf("重复元素(原地标记法): ");
    for (int i = 0; i 

输出结果：重复元素(原地标记法): 2 3

前提条件：数组元素为1到n-1的正整数，且允许修改原数据。

七、多重复元素统计

若需统计每个元素的重复次数，哈希表法最为直接。以下C++示例展示如何构建频率字典：

#include 
#include 

输出结果：

元素频率:

1: 1次

2: 2次

3: 1次

5: 3次

八、性能对比与选择建议

| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |

|--------------|------------|------------|------------------------------|

| 暴力枚举 | O(n²) | O(1) | 超小规模数据(n

| 排序+扫描 | O(n log n) | O(1) | 中等规模数据，需稳定排序 |

| 哈希表 | O(n) | O(n) | 大规模数据，需快速查找 |

| 位运算 | O(n) | O(1) | 元素范围0-31的整数 |

| 原地标记 | O(n) | O(1) | 正整数数组且允许修改原数据 |

实际开发中，若使用C++标准库，unordered_map通常是首选；若需极致性能且数据范围有限，可考虑位运算或原地标记法。

九、边界条件处理

1. 空数组：直接返回空结果

2. 所有元素唯一：正确返回无重复

3. 超大整数：哈希表需处理碰撞，排序法需选择大整数排序算法

4. 内存限制：嵌入式系统中需避免哈希表的动态内存分配

示例：安全检查的哈希表实现

#include 
#include 
#define MAX_NUM 1000
bool findDuplicateSafe(int arr[], int n) {
    bool exists[MAX_NUM + 1] = {false};
    for (int i = 0; i  MAX_NUM) {
            printf("错误: 元素超出范围0-%d\n", MAX_NUM);
            return false;
        }
        if (exists[arr[i]]) {
            printf("找到重复元素: %d\n", arr[i]);
            return true;
        }
        exists[arr[i]] = true;
    }
    printf("无重复元素\n");
    return false;
}
int main() {
    int arr1[] = {1, 2, 3, 4};
    int arr2[] = {1, 2, 2, 3};
    findDuplicateSafe(arr1, 4);
    findDuplicateSafe(arr2, 4);
    return 0;
}

十、总结与扩展应用

查找重复元素是算法设计中的经典问题，其解决方案体现了时间与空间复杂度的权衡艺术。从基础的双循环到高级的哈希优化，每种方法都有其适用场景。实际开发中，应结合数据规模、元素范围、内存限制等因素综合选择。

扩展应用包括：

1. 数据库去重：使用布隆过滤器处理海量数据

2. 网络安全：检测异常登录IP的重复尝试

3. 图像处理：查找重复的像素模式

4. 机器学习：识别训练数据中的重复样本

关键词：数组重复元素、C/C++算法、哈希表、排序优化、位运算、时间复杂度、空间复杂度、原地标记法

简介：本文系统探讨C/C++中查找数组重复元素的多种算法，涵盖暴力枚举、排序预处理、哈希表优化、位运算技巧及原地标记法，分析各方法的时间复杂度与空间复杂度，提供完整代码实现与性能对比，适用于数据清洗、统计分析和算法优化等场景。