Fork me on GitHub

【LeetCode】Contains Duplicate

217. Contains Duplicate

解法一、基于排序

对于给定的数组先排序然后再顺序查找有无重复,时间复杂度O(nlogn)。

217.contains-duplicate.cpplink
13
14
15
16
17
18
19
20
21
22
bool containsDuplicate_Sorting(vector<int> &nums)
{
sort(nums.begin(), nums.end());
for (int i = 1; i < nums.size(); i++)
{
if (nums[i - 1] == nums[i])
return true;
}
return false;
}

这里直接使用了STL库中sort()函数,其STL的sort()底层算法,数据量大时采用Quick Sort,分段递归排序,一旦分段后的数据量小于某个门槛,为避免Quick Sort的递归调用带来过大的额外负荷,就改用Insertion Sort。如果递归层次过深,还会改用Heap Sort
参考详细解说 STL 排序(Sort)

解法二、基于Hash表

将数组中的元素转换到Hash表当中时间复杂度O(n).

217.contains-duplicate.cpplink
24
25
26
27
28
bool containsDuplicate_HashTable(vector<int> &nums)
{
unordered_set<int> set(nums.begin(), nums.end());
return set.size() != nums.size();
}

C++ STL中Hash Table对应的数据结构是,查找某元素是否在unordered_set当中的方法是const bool is_in = container.find(element) != container.end();底层对应的数据结构是红黑树

219. Contains Duplicate II

220. Contains Duplicate III

您的支持将鼓励我继续创作!
0%