3318. 计算子数组的 x-sum I

🟢   🔖  数组 哈希表 滑动窗口 堆（优先队列）  🔗 力扣 LeetCode

题目

You are given an array nums of n integers and two integers k and x.

The x-sum of an array is calculated by the following procedure:

• Count the occurrences of all elements in the array.
• Keep only the occurrences of the top x most frequent elements. If two elements have the same number of occurrences, the element with the bigger value is considered more frequent.
• Calculate the sum of the resulting array.

Note that if an array has less than x distinct elements, its x-sum is the sum of the array.

Return an integer array answer of length n - k + 1 where answer[i] is the x-sum of the subarray nums[i..i + k - 1].

Example 1:

Input: nums = [1,1,2,2,3,4,2,3], k = 6, x = 2

Output: [6,10,12]

Explanation:

• For subarray [1, 1, 2, 2, 3, 4], only elements 1 and 2 will be kept in the resulting array. Hence, answer[0] = 1 + 1 + 2 + 2.
• For subarray [1, 2, 2, 3, 4, 2], only elements 2 and 4 will be kept in the resulting array. Hence, answer[1] = 2 + 2 + 2 + 4. Note that 4 is kept in the array since it is bigger than 3 and 1 which occur the same number of times.
• For subarray [2, 2, 3, 4, 2, 3], only elements 2 and 3 are kept in the resulting array. Hence, answer[2] = 2 + 2 + 2 + 3 + 3.

Example 2:

Input: nums = [3,8,7,8,7,5], k = 2, x = 2

Output: [11,15,15,15,12]

Explanation:

Since k == x, answer[i] is equal to the sum of the subarray nums[i..i + k - 1].

Constraints:

• 1 <= n == nums.length <= 50
• 1 <= nums[i] <= 50
• 1 <= x <= k <= nums.length

题目大意

给你一个由 n 个整数组成的数组 nums，以及两个整数 k 和 x。

数组的 x-sum 计算按照以下步骤进行：

• 统计数组中所有元素的出现次数。
• 仅保留出现次数最多的前 x 个元素的每次出现。如果两个元素的出现次数相同，则数值较大 的元素被认为出现次数更多。
• 计算结果数组的和。

注意 ，如果数组中的不同元素少于 x 个，则其 x-sum 是数组的元素总和。

返回一个长度为 n - k + 1 的整数数组 answer，其中 answer[i] 是 子数组 nums[i..i + k - 1] 的 x-sum 。

子数组 是数组内的一个连续非空 的元素序列。

示例 1：

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

输出：[6,10,12]

解释：

• 对于子数组 [1, 1, 2, 2, 3, 4]，只保留元素 1 和 2。因此，answer[0] = 1 + 1 + 2 + 2。
• 对于子数组 [1, 2, 2, 3, 4, 2]，只保留元素 2 和 4。因此，answer[1] = 2 + 2 + 2 + 4。注意 4 被保留是因为其数值大于出现其他出现次数相同的元素（3 和 1）。
• 对于子数组 [2, 2, 3, 4, 2, 3]，只保留元素 2 和 3。因此，answer[2] = 2 + 2 + 2 + 3 + 3。

示例 2：

输入： nums = [3,8,7,8,7,5], k = 2, x = 2

输出：[11,15,15,15,12]

解释：

由于 k == x，answer[i] 等于子数组 nums[i..i + k - 1] 的总和。

提示：

• 1 <= n == nums.length <= 50
• 1 <= nums[i] <= 50
• 1 <= x <= k <= nums.length

解题思路

• 可以使用滑动窗口的方式来计算每个长度为 k 的子数组的 x 和。滑动窗口的思想是在计算某个子数组时，通过移动窗口边界来避免重复计算每个元素的频率。
• 使用哈希表（字典）来存储每个元素的频率。每当窗口右移时，更新加入和移除的元素的频率。
• 每次更新完窗口后，根据每个元素的频率进行排序，并获取窗口中出现次数最多的前 x 个元素，计算前 x 个元素的和。
• 依次计算所有子数组的 x 和 ，并存入结果数组 answer 中，最后返回。

复杂度分析

• 时间复杂度：O((n - k + 1) * k log k)，其中 n 是数组 nums 的长度，k 是滑动窗口的长度。因为需要在长度为 k 的滑动窗口中维护频率并排序，以获取前 x 个最大频率的元素。
• 空间复杂度：O(k)，需要 O(k) 的空间来存储哈希表和数组。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @param {number} x
 * @return {number[]}
 */
var findXSum = function (nums, k, x) {
	let n = nums.length;
	let answer = [];
	// 维护元素的频率
	let freq = new Map();

	// 滑动窗口
	for (let i = 0; i < n; i++) {
		// 加入新元素
		freq.set(nums[i], (freq.get(nums[i]) || 0) + 1);

		// 如果窗口超出大小，移除最左边的元素
		if (i >= k) {
			let leftElem = nums[i - k];
			freq.set(leftElem, freq.get(leftElem) - 1);
			if (freq.get(leftElem) === 0) {
				freq.delete(leftElem);
			}
		}

		// 计算当前窗口的 x 和
		if (i >= k - 1) {
			// 排序
			let arr = [...freq.entries()].sort((a, b) => {
				if (a[1] === b[1]) {
					return b[0] - a[0];
				}
				return b[1] - a[1];
			});

			let sum = 0;
			for (let j = 0; j < Math.min(x, arr.length); j++) {
				sum += arr[j][0] * arr[j][1];
			}

			answer.push(sum);
		}
	}

	return answer;
};