Easy

题目描述

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

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

  1. 统计数组中所有元素的出现次数。
  2. 只保留出现次数最多的前 x 个不同元素的出现次数。如果两个元素的出现次数相同，则认为数值较大的元素更频繁。
  3. 计算结果数组的和。

注意，如果数组中不同元素的个数少于 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 = 6。
  • 对于子数组 [1, 2, 2, 3, 4, 2]，只有元素 2 和 4 会保留在结果数组中。因此，answer[1] = 2 + 2 + 2 + 4 = 10。注意 4 被保留在数组中，因为它比出现次数相同的 3 和 1 更大。
  • 对于子数组 [2, 2, 3, 4, 2, 3]，只有元素 2 和 3 被保留在结果数组中。因此，answer[2] = 2 + 2 + 2 + 3 + 3 = 12。

示例 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-sum。解决思路如下：

首先理解 x-sum 的计算规则：统计子数组中各元素出现次数，选择出现次数最多的前 x 个不同元素，如果出现次数相同则优先选择数值更大的元素，最后计算这些选中元素的总和。

解法一：直接模拟 对于每个子数组，用哈希表统计元素频次，然后按照 (频次, 数值) 排序，选择前 x 个元素计算和。时间复杂度为 O(nklog k)。

解法二：滑动窗口优化 使用滑动窗口维护当前子数组的元素频次，每次移动窗口时更新频次统计。对于每个窗口，仍需要排序选择前 x 个元素。

由于题目约束较小（n ≤ 50），直接模拟就足够高效。核心步骤是：

  1. 遍历所有长度为 k 的子数组
  2. 统计每个子数组中元素的出现次数
  3. 按照题目规则排序并选择前 x 个元素
  4. 计算选中元素的总和

代码实现

class Solution {
public:
    vector<int> findXSum(vector<int>& nums, int k, int x) {
        int n = nums.size();
        vector<int> answer;
        
        for (int i = 0; i <= n - k; i++) {
            unordered_map<int, int> freq;
            
            // 统计当前子数组的频次
            for (int j = i; j < i + k; j++) {
                freq[nums[j]]++;
            }
            
            // 将元素按照 (频次, 数值) 排序
            vector<pair<int, int>> elements;
            for (auto& p : freq) {
                elements.push_back({p.first, p.second});
            }
            
            sort(elements.begin(), elements.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
                if (a.second == b.second) {
                    return a.first > b.first;  // 频次相同时，数值大的在前
                }
                return a.second > b.second;    // 频次大的在前
            });
            
            // 计算前 x 个元素的和
            int sum = 0;
            int count = min(x, (int)elements.size());
            for (int j = 0; j < count; j++) {
                sum += elements[j].first * elements[j].second;
            }
            
            answer.push_back(sum);
        }
        
        return answer;
    }
};

class Solution:
    def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
        n = len(nums)
        answer = []
        
        for i in range(n - k + 1):
            # 统计当前子数组的频次
            freq = {}
            for j in range(i, i + k):
                freq[nums[j]] = freq.get(nums[j], 0) + 1
            
            # 按照 (频次, 数值) 排序
            elements = list(freq.items())
            elements.sort(key=lambda x: (-x[1], -x[0]))
            
            # 计算前 x 个元素的和
            total = 0
            count = min(x, len(elements))
            for j in range(count):
                total += elements[j][0] * elements[j][1]
            
            answer.append(total)
        
        return answer

public class Solution {
    public int[] FindXSum(int[] nums, int k, int x) {
        int n = nums.Length;
        int[] answer = new int[n - k + 1];
        
        for (int i = 0; i <= n - k; i++) {
            Dictionary<int, int> freq = new Dictionary<int, int>();
            
            // 统计当前子数组的频次
            for (int j = i; j < i + k; j++) {
                if (freq.ContainsKey(nums[j])) {
                    freq[nums[j]]++;
                } else {
                    freq[nums[j]] = 1;
                }
            }
            
            // 将元素按照 (频次, 数值) 排序
            var elements = freq.ToList();
            elements.Sort((a, b) => {
                if (a.Value == b.Value) {
                    return b.Key.CompareTo(a.Key);  // 频次相同时，数值大的在前
                }
                return b.Value.CompareTo(a.Value);  // 频次大的在前
            });
            
            // 计算前 x 个元素的和
            int sum = 0;
            int count = Math.Min(x, elements.Count);
            for (int j = 0; j < count; j++) {
                sum += elements[j].Key * elements[j].Value;
            }
            
            answer[i] = sum;
        }
        
        return answer;
    }
}

var findXSum = function(nums, k, x) {
    const result = [];
    
    for (let i = 0; i <= nums.length - k; i++) {
        const subarray = nums.slice(i, i + k);
        const freq = new Map();
        
        // Count frequencies
        for (const num of subarray) {
            freq.set(num, (freq.get(num) || 0) + 1);
        }
        
        // Convert to array and sort by frequency (desc) then by value (desc)
        const freqArray = Array.from(freq.entries());
        freqArray.sort((a, b) => {
            if (a[1] !== b[1]) return b[1] - a[1]; // frequency desc
            return b[0] - a[0]; // value desc
        });
        
        // Take top x elements and calculate sum
        let sum = 0;
        const topX = Math.min(x, freqArray.length);
        
        for (let j = 0; j < topX; j++) {
            const [value, count] = freqArray[j];
            sum += value * count;
        }
        
        result.push(sum);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O((n-k+1) × k × log k)
空间复杂度O(k)

其中 n 是数组长度。对于每个子数组，需要 O(k) 时间统计频次，O(k log k) 时间排序，共有 (n-k+1) 个子数组。空间复杂度主要用于存储频次统计和排序数组。