数据结构与算法--1.判断数组中元素是否有重复
在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)(需处理冲突)。
更多推荐


所有评论(0)