你很德布罗意的技术博客

判断数组中是否存在重复元素

1. 问题描述

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

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

示例 1:

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

示例 2:

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

示例 3:

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

作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x248f5/

2. 问题分析

  • 最初看到这道题的时候看这么少字,以为很简单,结果开始试了几种方法都是超时~开始肯定是国际惯例,从最简单粗暴的方式入手,要判断是否有重复元素只需要每一个元素都和其他元素比较一次就行了,于是可以用双循环的方法来搜索,发现有相同元素返回即可,但这种方法通常都只适用数据量小的情况,毕竟时间复杂度是O(n^2)呢,果不其然测试用例里有一个30万项左右的输入数组。。。于是双循环法肯定是超时了。
  • 既然双循环不行,我想能不能先把数组排个序,排序之后判断相邻元素是否相同即可解决。于是先试用冒泡排序,但毕竟也是O(n^2)的算法,冒泡排序也当然超时了。
  • 于是可以直接用std::sort函数进行排序,sort函数底层应该是用快速排序,平均时间复杂度为O(nlogn),果然使用sort函数可以通过最后一个大量项数的用例了。
  • 然后再试了一下最初想到的方法之一,将每个数字出现的次数用std::map计数,当出现第2次的时候即可判断重复,这种方法虽然可以通过,但无论时执行用时还是内存消耗都不理想,应该是把资源都耗费在map的建立和维持上了。
  • 最后试着用堆排序来实现排序部分算法,之后再通过比较相邻元素是否相同来解决,堆排序的时间复杂度为为O(nlogn),运行效果和使用std::sort大致一样。

3. 代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

class Solution {
public:
// 暴力解法
static bool containsDuplicate1(vector<int>& nums) {
if(nums.size() <= 1)
{
return false;
}
for(int i = 0; i < nums.size(); i++)
{
for(int j = i + 1; j < nums.size(); j++)
{
if(nums[i] == nums[j])
{
return true;
}
}
}
return false;
};
// 先冒泡排序,再判断重复
static bool containsDuplicate2(vector<int>& nums) {
if(nums.size() <= 1)
{
return false;
}
int len = nums.size();
while(len > 1)
{
for(int i = 0; i < nums.size() - 1; ++i)
{
if(nums[i] == nums[i + 1])
{
return true;
}
if(nums[i] > nums[i + 1])
{
int tmp = nums[i];
nums[i] = nums[i + 1];
nums[i + 1] = tmp;
}
}
--len;
}

for(int i = 0; i < nums.size() - 1; ++i)
{
if(nums[i] == nums[i + 1])
{
return true;
}
}

return false;
};
// 使用哈希表存放每个数出现次数
static bool containsDuplicate3(vector<int>& nums) {
if(nums.size() <= 1)
{
return false;
}
map<int, int> a;
for(int i = 0; i < nums.size(); i++)
{
a[nums[i]] = 0;
}
for(int i = 0; i < nums.size(); i++)
{
int idx = nums[i];
++a[idx];
if(a[idx] > 1)
{
return true;
}
}
return false;
};
// std::sort排序后比较
static bool containsDuplicate4(vector<int>& nums) {
if(nums.size() <= 1)
{
return false;
}
std::sort( nums.begin(), nums.end());
for(int i = 0; i < nums.size() - 1; i++)
{
if(nums[i] == nums[i + 1])
{
return true;
}
}
return false;
}
// 堆排序后比较
static bool containsDuplicate5(vector<int>& nums) {
if(nums.size() <= 1)
{
return false;
}

// 交换数组两个位置的值
auto swap_item = [](vector<int>& nums, int pos1, int pos2)
{
int tmp = nums[pos1];
nums[pos1] = nums[pos2];
nums[pos2] = tmp;
};

// 从某个结点pos开始调整堆
auto heap_sort = [=](vector<int>& nums, int pos, int len)
{
int dad = pos;
int son = 2 * pos + 1;
while(son < len)
{
// 找出最大子结点的值
if(son + 1 < len && nums[son + 1] > nums[son])
{
++son;
}
if(nums[son] <= nums[dad])
{
return;
}
else
{
swap_item(nums, son, dad);
dad = son;
son = 2 * dad + 1;
}
}
};

// 堆排序
auto myHeapSort = [=](vector<int>& nums)
{
// 先构造大顶堆
int len = nums.size();
for(int i = len / 2 - 1; i >= 0; --i)
{
heap_sort(nums, i, len);
}
// 先交换堆顶元素和最后一个元素,然后缩短数组,继续堆排序前面的数组
for(int i = nums.size() - 1; i >= 0; --i)
{
swap_item(nums, 0, i);
heap_sort(nums, 0, i);
}
};

myHeapSort(nums);
for(int i = 0; i < nums.size() - 1; i++)
{
if(nums[i] == nums[i + 1])
{
return true;
}
}
return false;
};
};

int main()
{
// int a[1] = {1};
// vector<int> nums(a, a + 1);
int a[10] = {1,1,1,3,3,4,3,2,4,2};
vector<int> nums(a, a + 10);
cout << "contains duplicate ? : " << Solution::containsDuplicate5(nums) << endl; // 1
for(auto it : nums)
{
cout << it << " "; // 1 1 1 2 2 3 3 3 4 4
}
cout << endl;
}

堆排序在远古时期好像学过,现在重新认真学习一下,看看明天专门写一篇文章来说明堆排序的具体操作,分析一下他的时间复杂度吧。


专题:

本文发表于 2020-10-27,最后修改于 2020-10-28。

本站永久域名www.namidame.tech,也可搜索「 你很德布罗意的技术博客 」找到我。

欢迎关注我的 微博 ,查看最近的文章和动态。


上一篇 « 旋转数组 下一篇 » 图解堆排序

赞赏支持

客官,打赏一个呗~

i ali

支付宝

i wechat

微信

推荐阅读

Big Image