Given a list of integers nums and an integer k, return a list of count of distinct numbers in each window of size k.
Constraints
1 ≤ k ≤ n ≤ 100,000 where n is length of nums.
Example 1
Input
nums = [1, 1, 2, 2, 3]
k = 2
Output
[1, 2, 1, 2]
Explanation
The windows are [1, 1], [1, 2], [2, 2], and [2, 3].
Slding Window Algorithm to Compute the K Distinct Window
We can use a sliding window which keeps the size of the distinct window. If the number of the distinct window is more than K, we move the left pointer.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | vector<int> kDistinctWindow(vector<int>& nums, int k) { int n = nums.size(); if (0 == n) return {}; vector<int> res; unordered_map<int, int> w; for (int i = 0; i < n; ++ i) { w[nums[i]] ++; if (i >= k) { if (--w[nums[i - k]] == 0) { w.erase(nums[i - k]); } } if (i >= k - 1) { res.push_back(w.size()); } } return res; } |
vector<int> kDistinctWindow(vector<int>& nums, int k) {
int n = nums.size();
if (0 == n) return {};
vector<int> res;
unordered_map<int, int> w;
for (int i = 0; i < n; ++ i) {
w[nums[i]] ++;
if (i >= k) {
if (--w[nums[i - k]] == 0) {
w.erase(nums[i - k]);
}
}
if (i >= k - 1) {
res.push_back(w.size());
}
}
return res;
}The time complexity is O(N) and the space complexity is O(N) where N is the number of elements in the array.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
275 wordsloading...
Last Post: Teaching Kids Programming - Compute the Hamming Distance of Two Integers
Next Post: Teaching Kids Programming - Recursive Algorithm to Merge Two Binary Trees
