leetcode，存在重复元素

发表于2020-03-21更新于2021-03-14

问题

刷leetcode时遇到一个很简单的问题：
给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。

示例1：

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

我的思路

作为leetcode的初学者，看到这个问题的第一眼感觉甚是简单。
代码写的也是简单暴力洋洋洒洒：

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

运行一下也是完全ok
不过提交时，却提醒超时。
看到我这个O(n^2+)的时间复杂度。属实无脑了些；
于是改进了一下：

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

可是这个时间复杂度度还是n^2呀。。。

便偷偷看了官方给的思路：

官方给的建议

Leetcode
哈哈，我这些小九九都被猜到了

总结

本以为这是个很简单的问题，看了官方解答证明了它的确是一个很简单的问题。不过我却被自己狭隘的大脑封印，明明都会的知识却不能很好的融会贯通。这道题是对自己的无情嘲讽又点亮了我的脑瓜（是的！我变强啦）。

答案

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
bool containsDuplicate(int* nums, int numsSize){
    if(numsSize > 0){
        bubbleSort(nums,numsSize);
        for(int i = 0;i < numsSize -1;i++){
            if(nums[i] == nums[i + 1]) return true;
        }
    }
    return false; 
}


void bubbleSort(int *dataArray,int n){
    int flag = 0;
    int i,j,temp;
    for(i = 0;i < n - 1;i++){
        flag == 0;
        for(j = 0;j < n  - 1;j++){	
            if(dataArray[j] > dataArray[j + 1]){
                flag = 1;
                temp = dataArray[j];
                dataArray[j] = dataArray[j + 1];
                dataArray[j + 1] = temp;
            }
        }
        if(flag == 0) break;
    }
}