「LeetCode」——217.存在重复元素

题面

给定一个整数数组,判断是否存在重复元素。

如果任意一值在数组中出现至少两次,函数返回 true 。如果数组中每个元素都不相同,则返回 false

示例 1:

1
2
输入: [1,2,3,1]
输出: true

示例 2:

1
2
输入: [1,2,3,4]
输出: false

示例 3:

1
2
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true

题解

暴力解法

1
2
3
4
5
6
7
8
9
bool containsDuplicate(int* nums, int numsSize) {
for(int i = 0; i < numsSize; i++){
for(int j = i+1; j <numsSize;j++){
if(nums[j] == nums[i])
return true;
}
}
return false;
}

这暴力一波,时间复杂度O(n^2)不出所料超时了。

哈希映射

其实就是一个比较常规的哈希映射,只是看用什么方法来优化这个哈希映射。

不考虑冲突(无法通过全部测试)

1
2
3
4
5
6
7
8
9
10
11
12
bool containsDuplicate(int* nums, int numsSize){
if (numsSize <= 1)return false;
if (nums[0] == nums[1])return true;
int hashtable[50000]={0},hash=0;
for(int i = 0; i < numsSize; i++){
hash=(nums[i]+120000006)%49999;
if(hashtable[hash]>0)
return true;
hashtable[hash]+=1;
}
return false;
}

可以看出来部分数据是存在冲突的,所以考虑一下处理冲突的方法。

哈希链表处理冲突 224ms 10.5mb

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
typedef struct __HashNode HashNode;
struct __HashNode {
int num;
HashNode* next;
};
bool hashadd(HashNode** Table, int num) {
HashNode* temp = (HashNode*)malloc(sizeof(HashNode));
int hash = (num + 120000006) % 97;
HashNode* p = Table[hash];
temp->num = num;
temp->next = NULL;
for (; p; p = p->next) {
if (num == p->num)
return true;
}
if (Table[hash]->next)
temp->next = Table[hash]->next;
Table[hash]->next = temp;
return false;
}
bool containsDuplicate(int* nums, int numsSize) {
if (numsSize <= 1)return false;
if (nums[0] == nums[1])return true;
HashNode** table = (HashNode**)malloc(sizeof(HashNode*) * 100);
for (int i = 0; i < 100; i++) {
table[i] = (HashNode*)malloc(sizeof(HashNode));
table[i]->num = -1;
table[i]->next = NULL;
}
for (int i = 0; i < numsSize; i++) {
if (hashadd(table, nums[i]))
return true;
}
return false;
}

哈希链表操作比较繁琐,导致时间上依然显得有点慢,不妨把链表变成二维数组来试试。

二维数组哈希表处理冲突

先贴一下测试结果:

1
2
3
4
5
//暴力调参
//hashtable[110][110] 52ms 8.1mb
//hashtable[1000][50] 28ms 8.1mb
//hashtable[10000][3] 20ms 7.7mb
//hashtable[5000][3] 16ms 8.0mb

可见数组的参数选择对时间的影响还是很大的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
bool containsDuplicate(int* nums, int numsSize){
if (numsSize <= 1)return false;
if (nums[0] == nums[1])return true;
int hashtable[110][110]={0};
int hash=0,flag=0;
for(int i=0; i < numsSize; i++){
if(nums[i]!=0){
hash=(nums[i]+120000006)%97;
for(int j=0; j < 110; j++){
if(hashtable[hash][j]==nums[i]){
return true;
}
else if(hashtable[hash][j]==0){
hashtable[hash][j]=nums[i];
break;
}
}
}
else{
if(flag==1)
return true;
flag=1;
}
}
return false;
}

「LeetCode」——217.存在重复元素
https://jason-xy.github.io/2020/07/leetcode-217/
作者
Jason Hsu
发布于
2020年7月2日
许可协议