题目
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：
输入：nums = [1,2,3,1]
输出：true
示例 2：
输入：nums = [1,2,3,4]
输出：false
示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true
解法
一.个人方法，使用map<int, string>作hashmap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
map<int, string> mmap;
string flag = "y";
for(int i=0; i<nums.size(); i++)
{
if(mmap[nums[i]] == flag)
return true;
mmap[nums[i]] = flag;
}
return false;
}
};
|
二.先排序，然后检查相邻是否相等重复
1
2
3
4
5
6
7
8
9
| bool containDuplicate(vector<int>& nums){
sort(nums.begin(), nums.end());
int n = nums.size();
for(int i=0; i<n-1;i++){
if(nums[i] == nums[i+1])
return true;
}
return false;
}
|
三.用unordered_set的哈希表
1
2
3
4
5
6
7
8
9
| bool containDuplicate(vector<int>& nums){
unordered_set<int> s;
for(int x:nums){
if(s.find(x)!=s.end())
return true;
s.insert(x);
}
return false;
}
|
相关知识
map
关联容器，一对一，第一个关键字只能出现一次，内部为自建红黑数（非严格平衡二叉树），可对数据自动排序。
map的特点时增删节点开销小，迭代器可以修改value,但不能修改key.查找数据复杂度为Log(N)
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
| #include <map>
std::map<int, string> mStudent;
mStudent.insert(pair<int, string>(1,"stu_one"));
mStudent.insert(pair<int, string>(2,"stu_two"));
mStudent.insert(map<int, string>::value_type(3,"stu_three"));
mStudent[4] = "stu_four";
map<int, string>::iterator iter;
for(iter = mStudent.begin(); iter != mStudent.end(); iter++)
cout <<iter->first<<' ' << iter->second << endl;
pair<map<int, string>::iterator, bool> Insert_Pair;
Insert_Pair = mStudent.insert(pair<int, string>(1,"stu_one"));
int nSize = mStudent.size();
map<int, string>::iterator iter;
iter = mStudent.find(1);
if(iter==mStudent.end())
cout <<"not found";
else
mStudent.erase(iter);
|
C++ maps是一种关联式容器，包含“关键字/值”对
begin() 返回指向map头部的迭代器
clear(） 删除所有元素
count() 返回指定元素出现的次数
empty() 如果map为空则返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊条目的迭代器对
erase() 删除一个元素
find() 查找一个元素
get_allocator() 返回map的配置器
insert() 插入元素
key_comp() 返回比较元素key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
rbegin() 返回一个指向map尾部的逆向迭代器
rend() 返回一个指向map头部的逆向迭代器
size() 返回map中元素的个数
swap() 交换两个map
upper_bound() 返回键值>给定元素的第一个位置
value_comp() 返回比较元素value的函数
unordered_set
基于哈希表的unordered_set和unordered_map区别于基于红黑树的set和map，内部无须，查找效率O（1）用空间换时间。原型为unordered_set,key为任意基本类型，然后经过默认hash(key)转成size_t作为bucker.具体用法如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <unordered_set>
std::unordered_set<int> ms{1,2,3,4,5};
ms.insert(6);
ms.insert(7);
for(auto &s: ms)
cout << s << endl;
ms.erase(2);
cout << ms.count(2);
ms.find(3);
|