在C语言中,我们可以使用类似的方法来实现判断数组中是否有重复值的功能。由于C语言没有内置的哈希集合(如Python的set或C++的unordered_set),我们需要自己实现一个简单的哈希表或使用其他方法。

方法一:暴力法(双重循环)
时间复杂度:O(n²)
空间复杂度:O(1)

#include <stdbool.h>

bool containsDuplicate(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
}

说明:

使用双重循环比较每一对元素。

如果发现相同的元素,立即返回true。

遍历结束后仍未发现重复,返回false。

方法二:先排序后比较相邻元素
时间复杂度:O(n log n)(取决于排序算法)
空间复杂度:O(1)(如果原地排序)

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

// 比较函数,用于qsort
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

bool containsDuplicate(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), compare); // 使用标准库的快速排序
    for (int i = 0; i < numsSize - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return true;
        }
    }
    return false;
}

说明:

使用qsort对数组进行排序(时间复杂度一般为O(n log n))。

遍历排序后的数组,检查相邻元素是否相同。

如果发现相同,返回true;否则返回false。

方法三:简单哈希表(适用于元素范围较小的情况)
时间复杂度:O(n)
空间复杂度:O(k)(k为元素的范围)

如果已知数组元素的范围较小(例如0 <= nums[i] <= 1000),可以用数组模拟哈希表:

#include <stdbool.h>
#include <string.h>

bool containsDuplicate(int* nums, int numsSize) {
    // 假设元素范围为 0~1000
    bool seen[1001] = {false}; // 初始化所有值为false
    for (int i = 0; i < numsSize; i++) {
        if (seen[nums[i]]) {
            return true;
        }
        seen[nums[i]] = true;
    }
    return false;
}

说明:

初始化一个布尔数组seen,用于记录元素是否出现过。

遍历数组,如果seen[nums[i]]为true,说明重复,返回true。

否则,标记seen[nums[i]] = true。

遍历结束后返回false。

方法四:通用哈希表(适用于任意整数)
如果元素范围很大或未知,可以手动实现一个简单的哈希表(例如使用开放寻址法或链地址法)。以下是开放寻址法的简单实现:

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

#define TABLE_SIZE 10000

typedef struct {
    int key;
    bool used;
} HashEntry;

HashEntry hashTable[TABLE_SIZE];

// 哈希函数(简单取模)
int hash(int key) {
    return abs(key) % TABLE_SIZE;
}

bool containsDuplicate(int* nums, int numsSize) {
    memset(hashTable, 0, sizeof(hashTable)); // 初始化哈希表
    for (int i = 0; i < numsSize; i++) {
        int h = hash(nums[i]);
        while (hashTable[h].used) {
            if (hashTable[h].key == nums[i]) {
                return true;
            }
            h = (h + 1) % TABLE_SIZE; // 线性探测
        }
        hashTable[h].key = nums[i];
        hashTable[h].used = true;
    }
    return false;
}

说明:

定义一个哈希表hashTable,每个槽位存储一个键和是否使用的标志。

使用取模哈希函数计算位置。

如果发生冲突,使用线性探测(h = (h + 1) % TABLE_SIZE)寻找下一个空槽。

如果找到相同的键,返回true;否则插入键并标记为已使用。

遍历结束后返回false。

方法选择建议
小规模数据:暴力法(方法一)简单直接。

中等规模数据:排序法(方法二)更高效。

元素范围较小:数组哈希表(方法三)最快。

通用情况:手动实现哈希表(方法四),但代码较复杂。

完整测试代码

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

// 方法一:暴力法
bool containsDuplicate_bruteForce(int* nums, int numsSize) {
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
}

// 方法二:排序法
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

bool containsDuplicate_sort(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), compare);
    for (int i = 0; i < numsSize - 1; i++) {
        if (nums[i] == nums[i + 1]) {
            return true;
        }
    }
    return false;
}

// 方法三:数组哈希表(假设元素范围0~1000)
bool containsDuplicate_arrayHash(int* nums, int numsSize) {
    bool seen[1001] = {false};
    for (int i = 0; i < numsSize; i++) {
        if (seen[nums[i]]) {
            return true;
        }
        seen[nums[i]] = true;
    }
    return false;
}

// 方法四:通用哈希表
#define TABLE_SIZE 10000
typedef struct {
    int key;
    bool used;
} HashEntry;

HashEntry hashTable[TABLE_SIZE];

int hash(int key) {
    return abs(key) % TABLE_SIZE;
}

bool containsDuplicate_hashTable(int* nums, int numsSize) {
    memset(hashTable, 0, sizeof(hashTable));
    for (int i = 0; i < numsSize; i++) {
        int h = hash(nums[i]);
        while (hashTable[h].used) {
            if (hashTable[h].key == nums[i]) {
                return true;
            }
            h = (h + 1) % TABLE_SIZE;
        }
        hashTable[h].key = nums[i];
        hashTable[h].used = true;
    }
    return false;
}

int main() {
    int nums1[] = {1, 2, 3, 1};
    int nums2[] = {1, 2, 3, 4};
    int nums3[] = {1, 1, 1, 1};

    printf("Brute Force:\n");
    printf("%d\n", containsDuplicate_bruteForce(nums1, 4)); // 1 (true)
    printf("%d\n", containsDuplicate_bruteForce(nums2, 4)); // 0 (false)

    printf("Sort:\n");
    printf("%d\n", containsDuplicate_sort(nums1, 4)); // 1
    printf("%d\n", containsDuplicate_sort(nums2, 4)); // 0

    printf("Array Hash:\n");
    printf("%d\n", containsDuplicate_arrayHash(nums1, 4)); // 1
    printf("%d\n", containsDuplicate_arrayHash(nums2, 4)); // 0

    printf("Hash Table:\n");
    printf("%d\n", containsDuplicate_hashTable(nums1, 4)); // 1
    printf("%d\n", containsDuplicate_hashTable(nums2, 4)); // 0

    return 0;
}

输出

Brute Force:
1
0
Sort:
1
0
Array Hash:
1
0
Hash Table:
1
0

总结
暴力法:代码简单,但效率低。

排序法:时间O(n log n),空间O(1)或O(n)。

数组哈希表:时间O(n),空间O(k)(需已知元素范围)。

通用哈希表:时间O(n),空间O(m)(需处理冲突)。

更多推荐