题目
【学习计划 - 数据结构 - 第一天 - 数组】https://leetcode-cn.com/study-plan/data-structures/
https://leetcode-cn.com/problems/contains-duplicate/
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
程序样例
1
2
3
| bool containsDuplicate(int* nums, int numsSize){
}
|
方法一
关键代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
bool containsDuplicate(int* nums, int numsSize){
bool flag = false;
int temp;
for(int i=0;i<numsSize;i++){
if(flag == true){
break;
}
for(int j=0;j<numsSize-1-i;j++){
if(*(nums+j)>*(nums+j+1)){
temp = *(nums+j);
*(nums+j) = *(nums+j+1);
*(nums+j+1) = temp;
}
if(*(nums+j)==*(nums+j+1)){
flag = true;
break;
}
}
}
return flag;
}
|
思路：用冒泡排序排序，同时看有没有重复元素。
时间复杂度：$O(n^2)$
结果：超时
方法二
关键代码
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
| bool containsDuplicate(int* nums, int numsSize){
int min=0,max=0,temp;
for(int i=0;i<numsSize;i++){
temp = *(nums+i);
if(temp<min){
min = temp;
}
if(temp>max){
max = temp;
}
}
int num0[max-min+1];
for(int i=0;i<max-min+1;i++){
num0[i] =0;
}
for(int i=0;i<numsSize;i++){
temp = *(nums+i);
if(*(num0+temp-min)==1){
return true;
}
*(num0+temp-min)=1;
}
return false;
}
|
思路：桶排序。由于数组下标从0开始，而需要比较的数字中可以有负数，所以找到最小值，桶排序时的下标为数值-最小值。
坑：leetcode竟然没有把数组全部默认初始化为0，可能是初始化为随机数了。所以需要我再手动对桶数组初始化为0。
完整代码
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
36
37
38
39
40
41
42
43
44
45
| #include <stdio.h>
bool containsDuplicate(int* nums, int numsSize){
int min=0,max=0,temp;
for(int i=0;i<numsSize;i++){
temp = *(nums+i);
if(temp<min){
min = temp;
}
if(temp>max){
max = temp;
}
}
int num0[max-min+1];
for(int i=0;i<max-min+1;i++){
num0[i] =0;
}
for(int i=0;i<numsSize;i++){
temp = *(nums+i);
if(*(num0+temp-min)==1){
return true;
}
*(num0+temp-min)=1;
}
return false;
}
main(){
int numsSize=5;
int nums[]={1,5,-2,-4,0};
for(int i=0;i<numsSize;i++){
printf("%d\n",*(nums+i));
}
bool flag = containsDuplicate(nums,numsSize);
printf("--%d--\n",flag);
for(int i=0;i<numsSize;i++){
printf("%d\n",*(nums+i));
}
}
|
复杂度分析
执行用时：20 ms, 在所有 C 提交中击败了73.56%的用户
内存消耗：11.2 MB, 在所有 C 提交中击败了26.56%的用户