【LintCode 中等】692. 滑动窗口内唯一元素数量和

以你之姓@ 2023-01-17 10:58 94阅读 0赞

1. 描述

给一个数组和一个滑动窗口的大小, 求每一个窗口内只出现一次的元素的个数和

2. 样例

> 输入：  
> \[1, 2, 1, 3, 3\]  
> 3  
> 输出：5  
> 解释：  
> 第一个窗口为 \[1, 2, 1\], 只有 2 是唯一的, 计数为 1.  
> 第二个窗口为 \[2, 1, 3\], 所有的元素都是唯一的, 计数为 3.  
> 第三个窗口为 \[1, 3, 3\], 只有 1 是唯一的, 计数为 1.  
> 总数为 1 + 3 + 1 = 5

>  输入：  
> \[1, 2, 1, 2, 1\]  
> 3  
> 输出：3

3. 代码

本题考查滑动窗口的知识点，利用滑动窗口使得下一次得到结果可以利用上一次的结果，从而可以减少时间复杂度。

先根据nums中最大的数，生成一个全0的数组，用于存储nums中各子数组（滑动数组）中每个数的个数。下标即为数本身，值为数的个数。

注意当nums的个数小于k时候，即不用滑动，此时直接看nums中唯一元素个数和。

当nums个数大于k时候，需要不断滑动，更新子数组中唯一元素的个数情况。这里涉及到判断情况：

1）当新增元素和剔除元素相同时候，则本次唯一元素的个数等于上一次的结果

2）如果新增元素的个数为1，则表明之前没有此元素，将唯一元素数量增1；如果新增元素的个数为2，表明之前有此元素并且为1，故现在需要将唯一元素减1

3）如果剔除元素的个数为1，则表明之前该元素数量为2，现在成为了新的唯一元素，将唯一元素增1；如果剔除元素的个数为0，故之前是唯一元素，现在子数组中不含该元素，将唯一元素减1

class Solution:
        """
        @param nums: the given array
        @param k: the window size
        @return: the sum of the count of unique elements in each window
        """
        def slidingWindowUniqueElementsSum(self, nums, k):
            # write your code here
            maxlength = max(nums)
            count = []
            for i in range(maxlength):
                count.append(0)
    
            if len(nums)<=k:
                for i in range(len(nums)):
                    count[nums[i]-1]+=1
                res = self.calculate(count)
                return res
    
            for i in range(k):
                count[nums[i]-1]+=1
            res = self.calculate(count)
            result = []
            result.append(res)
            for i in range(k, len(nums)):
                sub = result[i-k]
                count[nums[i]-1]+=1
                count[nums[i-k]-1]-=1
                if nums[i] != nums[i-k]:
                    if count[nums[i]-1]==1:
                        sub +=1
                    elif count[nums[i]-1]==2:
                        sub -=1
                    if count[nums[i-k]-1]==1:
                        sub +=1
                    elif count[nums[i-k]-1]==0:
                        sub-=1
                result.append(sub)
                
            totalresult = 0
            for i in range(len(result)):
                totalresult += result[i]
            return totalresult
    
        def calculate(self, count):
            res = 0
            for i in range(len(count)):
                if count[i]==1:
                    res+=1
            return res
    
    
    
        #     res = self.count_unique(nums[:k])
        #     if len(nums)<=k:
        #         return res
        #     else:
        #         temp_list = nums[:k]
        #         print(temp_list)
        #         for i in range(k, len(nums)):
        #             temp_list.append(nums[i])
        #             temp_list.pop(0)
        #             res += self.count_unique(temp_list)
        #             print(res)
        #         return res
    
        # def count_unique(self, nums):
        #     count = 0
        #     temp_dict = {}
        #     for index in nums:
        #         if index not in temp_dict.keys():
        #             temp_dict[index] = 1
        #         else:
        #             temp_dict[index] +=1
            
        #     for value in temp_dict.values():
        #         if value ==1:
        #             count+=1
    
        #     return count