跳转至

3672. 子数组中加权众数的总和 🔒

题目描述

给定一个整数数组 nums 和一个整数 k。

对于每个长度为 k 的 子数组：

  • 众数 mode 是指 出现频率最高 的元素。如果有多个众数，取其中 最小 的那个元素。
  • 权重 定义为 mode * frequency(mode)。

返回长度为 k 的所有 子数组 的权重之 和。

注意：

  • 子数组 是数组中连续的 非空 元素序列。
  • 元素 x 的 频率 是它在数组中出现的次数。

 

示例 1：

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

输出：8

解释：

长度为 k = 3 的子数组是：

子数组 频率 众数 众数频率 权重
[1, 2, 2] 1: 1, 2: 2 2 2 2 × 2 = 4
[2, 2, 3] 2: 2, 3: 1 2 2 2 × 2 = 4

因此，权重的和是 4 + 4 = 8。

示例 2：

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

输出：3

解释：

长度为 k = 2 的子数组是：

子数组 频率 众数 众数频率 权重
[1, 2] 1: 1, 2: 1 1 1 1 × 1 = 1
[2, 1] 2: 1, 1: 1 1 1 1 × 1 = 1
[1, 2] 1: 1, 2: 1 1 1 1 × 1 = 1

因此，权重的和是 1 + 1 + 1 = 3。

示例 3：

输入：nums = [4,3,4,3], k = 3

输出：14

解释：

长度为 k = 3 的子数组是：

子数组 频率 众数 众数频率 权重
[4, 3, 4] 4: 2, 3: 1 4 2 2 × 4 = 8
[3, 4, 3] 3: 2, 4: 1 3 2 2 × 3 = 6

因此，权重的和是 8 + 6 = 14。

 

提示：

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

解法

方法一：哈希表 + 优先队列 + 滑动窗口 + 懒删除

我们用一个哈希表 \(\textit{cnt}\) 记录当前窗口中每个数字的出现次数。我们用一个优先队列 \(\textit{pq}\) 记录当前窗口中每个数字的出现次数和数字本身，优先级为出现次数从大到小，如果出现次数相同，则数字从小到大。

我们设计一个函数 \(\textit{get\_mode()}\)，用于获取当前窗口的众数及其出现次数。具体做法是不断弹出优先队列的堆顶元素，直到堆顶元素的出现次数与哈希表中记录的出现次数相同为止，此时堆顶元素即为当前窗口的众数及其出现次数。

我们用一个变量 \(\textit{ans}\) 记录所有窗口的权重和。初始时，我们将数组的前 \(k\) 个数字加入哈希表和优先队列中，然后调用 \(\textit{get\_mode()}\) 获取第一个窗口的众数及其出现次数，并将其权重加入 \(\textit{ans}\)。

然后，我们从数组的第 \(k\) 个数字开始，依次将每个数字加入哈希表和优先队列中，同时将窗口的左端数字从哈希表中删除（出现次数减一）。然后调用 \(\textit{get\_mode()}\) 获取当前窗口的众数及其出现次数，并将其权重加入 \(\textit{ans}\)。

最后，返回 \(\textit{ans}\)。

时间复杂度 \(O(n \log k)\)，其中 \(n\) 是数组的长度。空间复杂度 \(O(k)\)。

 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
class Solution:
    def modeWeight(self, nums: List[int], k: int) -> int:
        pq = []
        cnt = defaultdict(int)
        for x in nums[:k]:
            cnt[x] += 1
            heappush(pq, (-cnt[x], x))

        def get_mode() -> int:
            while -pq[0][0] != cnt[pq[0][1]]:
                heappop(pq)
            freq, val = -pq[0][0], pq[0][1]
            return freq * val

        ans = 0
        ans += get_mode()

        for i in range(k, len(nums)):
            x, y = nums[i], nums[i - k]
            cnt[x] += 1
            cnt[y] -= 1
            heappush(pq, (-cnt[x], x))
            heappush(pq, (-cnt[y], y))

            ans += get_mode()

        return ans

 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
39
40
class Solution {
    public long modeWeight(int[] nums, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));

        for (int i = 0; i < k; i++) {
            int x = nums[i];
            cnt.merge(x, 1, Integer::sum);
            pq.offer(new int[] {-cnt.get(x), x});
        }

        long ans = 0;

        Supplier<Long> getMode = () -> {
            while (true) {
                int[] top = pq.peek();
                int val = top[1];
                int freq = -top[0];
                if (cnt.getOrDefault(val, 0) == freq) {
                    return 1L * freq * val;
                }
                pq.poll();
            }
        };

        ans += getMode.get();

        for (int i = k; i < nums.length; i++) {
            int x = nums[i], y = nums[i - k];
            cnt.merge(x, 1, Integer::sum);
            pq.offer(new int[] {-cnt.get(x), x});
            cnt.merge(y, -1, Integer::sum);
            pq.offer(new int[] {-cnt.get(y), y});
            ans += getMode.get();
        }

        return ans;
    }
}

 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:
    long long modeWeight(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        priority_queue<pair<int, int>> pq; // {freq, -val}

        for (int i = 0; i < k; i++) {
            int x = nums[i];
            cnt[x]++;
            pq.push({cnt[x], -x});
        }

        auto get_mode = [&]() {
            while (true) {
                auto [freq, negVal] = pq.top();
                int val = -negVal;
                if (cnt[val] == freq) {
                    return 1LL * freq * val;
                }
                pq.pop();
            }
        };

        long long ans = 0;
        ans += get_mode();

        for (int i = k; i < nums.size(); i++) {
            int x = nums[i], y = nums[i - k];
            cnt[x]++;
            cnt[y]--;
            pq.push({cnt[x], -x});
            pq.push({cnt[y], -y});
            ans += get_mode();
        }

        return ans;
    }
};

 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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
func modeWeight(nums []int, k int) int64 {
    cnt := make(map[int]int)
    pq := &MaxHeap{}
    heap.Init(pq)

    for i := 0; i < k; i++ {
        x := nums[i]
        cnt[x]++
        heap.Push(pq, pair{cnt[x], x})
    }

    getMode := func() int64 {
        for {
            top := (*pq)[0]
            if cnt[top.val] == top.freq {
                return int64(top.freq) * int64(top.val)
            }
            heap.Pop(pq)
        }
    }

    var ans int64
    ans += getMode()

    for i := k; i < len(nums); i++ {
        x, y := nums[i], nums[i-k]
        cnt[x]++
        cnt[y]--
        heap.Push(pq, pair{cnt[x], x})
        heap.Push(pq, pair{cnt[y], y})
        ans += getMode()
    }

    return ans
}

type pair struct {
    freq int
    val  int
}

type MaxHeap []pair

func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool {
    if h[i].freq != h[j].freq {
        return h[i].freq > h[j].freq
    }
    return h[i].val < h[j].val
}
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x any) {
    *h = append(*h, x.(pair))
}
func (h *MaxHeap) Pop() any {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

评论