Leetcode 219 - Contains Duplicate II（hash or sort）

2019-11-08 19:49:59

字体：大中小

来源：转载

供稿：网友

题意

给定一个数组nums和一个数k，判断是否存在numsi=numsj $nums_i = nums_j$ 且|j−i|≤k $|j - i| /leq k$ 。

思路

算法1

建立一个pair<int, int>为numsi $nums_i$ 和i $i$ ，我们排序O(nlogn) $O(nlogn)$ 排序后遍历一遍就可以了。

算法2

用unordered_map存储元素x最后一次出现的下标，每次O(1) $O(1)$ 的去查找和判断就可以了。

时间复杂度O(n) $O(n)$ 。

代码

//algorithm 1class Solution {public: bool containsNearbyDuplicate(vector<int>& nums, int k) { vector<pair<int, int>> a; for (int i = 0; i < nums.size(); i++) a.push_back(make_pair(nums[i], i)); sort(a.begin(), a.end()); for (int i = 1; i < nums.size(); i++) { if (a[i].first == a[i - 1].first) if (abs(a[i].second - a[i - 1].second) <= k) return true; } return false; }};//algorithm 2class Solution {public: bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_map<int, int> vis; for (int i = 0; i < nums.size(); i++) { int x = nums[i]; if (vis.count(x)) { if (i - vis[x] <= k) return true; } vis[x] = i; } return false; }};

上一篇：Spring框架学习一

下一篇：菱形虚拟继承的深入剖析