Algorithm

LintCode/Sliding Window Unique Elements Sum

Problem Summary

Given an array and a window size that is sliding along the array, find the sum of the numbers of unique elements in each window.

Solution

We can use the container “unoreder_map” in STL to help us calculate the frequencies of numbers in the current window. It is actually using hash map (or hash table) to keep record of values, so the time complexity is O(N).

Code

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
37
38
class Solution {
public:
    /*
     * @param : the given array
     * @param : the window size
     * @return: the sum of the count of unique elements in each window
     */
    int slidingWindowUniqueElementsSum(vector<int> nums, int k) {
    	int n = nums.size();
    	if (n < k)
    		k = n;
    	if (k == 0)
    		return 0;
    	int ans = 0;
    	unordered_map<int,int> count;
    	for (int i = 0; i < k; ++i)
    		++count[nums[i]];	
    	for (unordered_map<int,int>::iterator it = count.begin(); it != count.end(); ++it)
    		if (it->second == 1)
    			++ans;
    	
    	for (int i = k; i < n; ++i)
    	{
    		--count[nums[i-k]];
    		++count[nums[i]];
    		if (count[nums[i-k]] == 0)
    			count.erase(nums[i-k]);
    		
    		for (unordered_map<int,int>::iterator it = count.begin(); it != count.end(); ++it)
	    		if (it->second == 1)
    				++ans;
    	}
    	return ans;
    }
};