跳转至

3837. 相等元素的延迟计数 🔒

题目描述

给定一个长度为 n 的整数数组 nums 和一个整数 k。

对于每个下标 i，将 延迟计数 定义为满足以下条件的索引 j 的数量：

  • i + k < j <= n - 1，且
  • nums[j] == nums[i]

返回一个数组 ans，其中 ans[i] 是下标 i 的 延迟计数。

 

示例 1：

输入：nums = [1,2,1,1], k = 1

输出：[2,0,0,0]

解释：

i nums[i] 可能的 j nums[j] 满足
nums[j] == nums[i]		 ans[i]
0 1 [2, 3] [1, 1] [2, 3] 2
1 2 [3] [1] [] 0
2 1 [] [] [] 0
3 1 [] [] [] 0

因此，ans = [2, 0, 0, 0]。

示例 2：

输入：nums = [3,1,3,1], k = 0

输出：[1,1,0,0]

解释：

i nums[i] 可能的 j nums[j] 满足
nums[j] == nums[i]		 ans[i]
0 3 [1, 2, 3] [1, 3, 1] [2] 1
1 1 [2, 3] [3, 1] [3] 1
2 3 [3] [1] [] 0
3 1 [] [] [] 0

因此，ans = [1, 1, 0, 0]​​​​​​​.

 

提示：

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

解法

方法一：哈希表 + 倒序枚举

我们可以使用一个哈希表 \(\textit{cnt}\) 来记录每个数字在索引范围 \((i + k, n - 1]\) 内出现的次数。我们从下标 \(n - k - 2\) 开始倒序枚举索引 \(i\)，在枚举的过程中先将索引 \(i + k + 1\) 处的数字加入哈希表 \(\textit{cnt}\) 中，然后将 \(\textit{cnt}[nums[i]]\) 的值赋给答案数组 \(\textit{ans}[i]\)。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(\textit{nums}\) 的长度。

1
2
3
4
5
6
7
8
9
class Solution:
    def delayedCount(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        cnt = Counter()
        ans = [0] * n
        for i in range(n - k - 2, -1, -1):
            cnt[nums[i + k + 1]] += 1
            ans[i] = cnt[nums[i]]
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int[] delayedCount(int[] nums, int k) {
        int n = nums.length;
        var cnt = new HashMap<Integer, Integer>();
        int[] ans = new int[n];
        for (int i = n - k - 2; i >= 0; --i) {
            cnt.merge(nums[i + k + 1], 1, Integer::sum);
            ans[i] = cnt.getOrDefault(nums[i], 0);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    vector<int> delayedCount(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> cnt;
        vector<int> ans(n);
        for (int i = n - k - 2; i >= 0; --i) {
            ++cnt[nums[i + k + 1]];
            ans[i] = cnt[nums[i]];
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func delayedCount(nums []int, k int) []int {
    n := len(nums)
    cnt := map[int]int{}
    ans := make([]int, n)
    for i := n - k - 2; i >= 0; i-- {
        cnt[nums[i+k+1]]++
        ans[i] = cnt[nums[i]]
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function delayedCount(nums: number[], k: number): number[] {
    const n = nums.length;
    const cnt = new Map<number, number>();
    const ans = Array(n).fill(0);
    for (let i = n - k - 2; i >= 0; i--) {
        cnt.set(nums[i + k + 1], (cnt.get(nums[i + k + 1]) ?? 0) + 1);
        ans[i] = cnt.get(nums[i]) ?? 0;
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
use std::collections::HashMap;

impl Solution {
    pub fn delayed_count(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let n = nums.len();
        let mut cnt: HashMap<i32, i32> = HashMap::new();
        let mut ans = vec![0; n];
        let k = k as usize;
        let mut i = n as i32 - k as i32 - 2;
        while i >= 0 {
            let idx = i as usize;
            *cnt.entry(nums[idx + k + 1]).or_insert(0) += 1;
            ans[idx] = *cnt.get(&nums[idx]).unwrap_or(&0);
            i -= 1;
        }
        ans
    }
}

评论