Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
Submit your solution: https://leetcode.com/problems/contains-duplicate-ii/
Using Map
We can use STL::map data structure to store the last index for a given number. Thus, we can check if the current index is within the k-window. We need to update at each iteration the last index.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_map<int, int> cache; for (int i = 0; i < nums.size(); i ++) { int cur = nums[i]; if (cache.count(cur)) { int last = cache[cur]; if (i - last <= k) { // at most k return true; } } cache[cur] = i; // updated the last index } return false; } }; |
class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_map<int, int> cache; for (int i = 0; i < nums.size(); i ++) { int cur = nums[i]; if (cache.count(cur)) { int last = cache[cur]; if (i - last <= k) { // at most k return true; } } cache[cur] = i; // updated the last index } return false; } };
Sliding Window
We can use unordered_set as well to store all numbers within the k-window. Then we need to update (insert or erase) numbers at each iteration.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_set<int> uset; int size = nums.size(); int w = 0; for(int i = 0;i < size; ++i){ if(i - w > k){ uset.erase(nums[w++]); // out of the sliding window } auto r = uset.insert(nums[i]); // include the new number if(!r.second) { return true; } } return false; } }; |
class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_set<int> uset; int size = nums.size(); int w = 0; for(int i = 0;i < size; ++i){ if(i - w > k){ uset.erase(nums[w++]); // out of the sliding window } auto r = uset.insert(nums[i]); // include the new number if(!r.second) { return true; } } return false; } };
Note that the STL::set.insert function returns the pair that the second value when equal false represents that the value has existed in the set before the insertion. It is equivalent to the following:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_set<int> uset; int size = nums.size(); int w = 0; for(int i = 0;i < size; ++i){ if(i - w > k){ uset.erase(nums[w++]); // out of the sliding window } if (uset.count(nums[i])) { return true; } uset.insert(nums[i]); } return false; } }; |
class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_set<int> uset; int size = nums.size(); int w = 0; for(int i = 0;i < size; ++i){ if(i - w > k){ uset.erase(nums[w++]); // out of the sliding window } if (uset.count(nums[i])) { return true; } uset.insert(nums[i]); } return false; } };
All above solutions have complexity O(n).
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Nth Highest Distinct Record using SQL
Next Post: How to Add Binary String in C/C++?
Do they? The complexities of the map and set functions are constant time are they?