Skip to content

Latest commit

 

History

History

1852.Distinct Numbers in Each Subarray

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 
 
 
 
 

English Version

题目描述

给你一个整数数组 nums与一个整数 k,请你构造一个长度 n-k+1 的数组 ans,这个数组第i个元素 ans[i] 是每个长度为k的子数组 nums[i:i+k-1] = [nums[i], nums[i+1], ..., nums[i+k-1]]中数字的种类数。

返回这个数组 ans

 

示例 1:

输入: nums = [1,2,3,2,2,1,3], k = 3
输出: [3,2,2,2,3]
解释:每个子数组的数字种类计算方法如下:
- nums[0:2] = [1,2,3] 所以 ans[0] = 3
- nums[1:3] = [2,3,2] 所以 ans[1] = 2
- nums[2:4] = [3,2,2] 所以 ans[2] = 2
- nums[3:5] = [2,2,1] 所以 ans[3] = 2
- nums[4:6] = [2,1,3] 所以 ans[4] = 3

示例 2:

输入: nums = [1,1,1,1,2,3,4], k = 4
输出: [1,2,3,4]
解释: 每个子数组的数字种类计算方法如下:
- nums[0:3] = [1,1,1,1] 所以 ans[0] = 1
- nums[1:4] = [1,1,1,2] 所以 ans[1] = 2
- nums[2:5] = [1,1,2,3] 所以 ans[2] = 3
- nums[3:6] = [1,2,3,4] 所以 ans[3] = 4

 

提示:

  • 1 <= k <= nums.length <= 105
  • 1 <= nums[i] <= 105

解法

方法一:滑动窗口 + 哈希表/数组

用数组或哈希表记录每个窗口大小为 $k$ 的子数组中的数字出现的次数,然后遍历数组,每次更新哈希表,并记录当前窗口中数字的种类数。

时间复杂度 $O(n)$,空间复杂度 $O(n)$,其中 $n$ 是数组的长度。

Python3

class Solution:
    def distinctNumbers(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        cnt = Counter(nums[:k])
        ans = [len(cnt)]
        for i in range(k, n):
            u = nums[i - k]
            cnt[u] -= 1
            if cnt[u] == 0:
                cnt.pop(u)

            cnt[nums[i]] += 1
            ans.append(len(cnt))
        return ans

Java

class Solution {
    public int[] distinctNumbers(int[] nums, int k) {
        int[] cnt = new int[100010];
        int x = 0;
        for (int i = 0; i < k; ++i) {
            if (cnt[nums[i]]++ == 0) {
                ++x;
            }
        }
        int n = nums.length;
        int[] ans = new int[n - k + 1];
        ans[0] = x;
        for (int i = k; i < n; ++i) {
            if (--cnt[nums[i - k]] == 0) {
                --x;
            }
            if (cnt[nums[i]]++ == 0) {
                ++x;
            }
            ans[i - k + 1] = x;
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> distinctNumbers(vector<int>& nums, int k) {
        int cnt[100010] = {0};
        int x = 0;
        for (int i = 0; i < k; ++i) {
            if (cnt[nums[i]]++ == 0) {
                ++x;
            }
        }
        int n = nums.size();
        vector<int> ans(n - k + 1);
        ans[0] = x;
        for (int i = k; i < n; ++i) {
            if (--cnt[nums[i - k]] == 0) {
                --x;
            }
            if (cnt[nums[i]]++ == 0) {
                ++x;
            }
            ans[i - k + 1] = x;
        }
        return ans;
    }
};

Go

func distinctNumbers(nums []int, k int) []int {
	cnt := map[int]int{}
	for _, v := range nums[:k] {
		cnt[v]++
	}
	ans := []int{len(cnt)}
	for i := k; i < len(nums); i++ {
		u := nums[i-k]
		cnt[u]--
		if cnt[u] == 0 {
			delete(cnt, u)
		}
		cnt[nums[i]]++
		ans = append(ans, len(cnt))
	}
	return ans
}

...