Hard
题目描述
给定一个由 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 = 6
- 对于子数组 [1, 2, 2, 3, 4, 2]，只保留元素 2 和 4。因此 answer[1] = 2 + 2 + 2 + 4 = 10
- 对于子数组 [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] 的总和。
约束条件：
- nums.length == n
- 1 <= n <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= x <= k <= nums.length
解题思路
这道题需要维护滑动窗口中前 x 个最频繁元素的和。关键在于使用两个有序集合（优先队列或平衡二叉搜索树）来维护元素的频次排序。
核心思路：
- 使用两个集合：
topX维护前 x 个最频繁的元素，rest维护其余元素 - 元素按
(频次, 值)排序，频次高的优先，频次相同时值大的优先 - 滑动窗口时，需要动态调整两个集合的内容并维护
topX中元素的总和
算法步骤：
- 初始化第一个窗口，计算每个元素的频次
- 将所有元素按优先级放入集合，维护
topX只包含前 x 个元素 - 滑动窗口时：
- 移除左边界元素，更新其频次
- 添加右边界元素，更新其频次
- 重新平衡两个集合，确保
topX包含优先级最高的 x 个元素 - 计算当前
topX的总和
实现细节：
- 使用哈希表记录频次
- 使用
set或multiset维护有序集合 - 每次元素频次变化时，需要从原集合中删除并重新插入
代码实现
class Solution {
public:
vector<long long> findXSum(vector<int>& nums, int k, int x) {
unordered_map<int, int> freq;
set<pair<int, int>> topX, rest;
long long topSum = 0;
int n = nums.size();
vector<long long> result;
auto addElement = [&](int val, int count) {
pair<int, int> p = {count, val};
if (topX.size() < x) {
topX.insert(p);
topSum += (long long)count * val;
} else {
auto minTop = *topX.begin();
if (p > minTop) {
topX.erase(minTop);
topSum -= (long long)minTop.first * minTop.second;
rest.insert(minTop);
topX.insert(p);
topSum += (long long)count * val;
} else {
rest.insert(p);
}
}
};
auto removeElement = [&](int val, int count) {
pair<int, int> p = {count, val};
if (topX.count(p)) {
topX.erase(p);
topSum -= (long long)count * val;
if (!rest.empty()) {
auto maxRest = *rest.rbegin();
rest.erase(maxRest);
topX.insert(maxRest);
topSum += (long long)maxRest.first * maxRest.second;
}
} else {
rest.erase(p);
}
};
// Initialize first window
for (int i = 0; i < k; i++) {
freq[nums[i]]++;
}
for (auto& [val, count] : freq) {
addElement(val, count);
}
result.push_back(topSum);
// Sliding window
for (int i = k; i < n; i++) {
// Remove left element
int left = nums[i - k];
if (freq[left] > 0) {
removeElement(left, freq[left]);
freq[left]--;
if (freq[left] > 0) {
addElement(left, freq[left]);
}
}
// Add right element
int right = nums[i];
if (freq[right] > 0) {
removeElement(right, freq[right]);
}
freq[right]++;
addElement(right, freq[right]);
result.push_back(topSum);
}
return result;
}
};
class Solution:
def findXSum(self, nums: List[int], k: int, x: int) -> List[int]:
from collections import defaultdict
import heapq
freq = defaultdict(int)
result = []
n = len(nums)
def get_priority(val, count):
return (-count, -val) # negative for max heap behavior
# Use two heaps to maintain top x elements
top_heap = [] # max heap for top x elements
rest_heap = [] # max heap for remaining elements
top_sum = 0
def add_to_top(val, count):
nonlocal top_sum
heapq.heappush(top_heap, get_priority(val, count))
top_sum += count * val
def add_to_rest(val, count):
heapq.heappush(rest_heap, get_priority(val, count))
def balance_heaps():
nonlocal top_sum
# Move excess elements from top to rest
while len(top_heap) > x:
neg_count, neg_val = heapq.heappop(top_heap)
count, val = -neg_count, -neg_val
top_sum -= count * val
add_to_rest(val, count)
# Move elements from rest to top if needed
while len(top_heap) < x and rest_heap:
neg_count, neg_val = heapq.heappop(rest_heap)
count, val = -neg_count, -neg_val
add_to_top(val, count)
# Initialize first window
for i in range(k):
freq[nums[i]] += 1
# Build initial heaps
items = [(val, count) for val, count in freq.items()]
items.sort(key=lambda x: (-x[1], -x[0])) # sort by frequency desc, then value desc
for i, (val, count) in enumerate(items):
if i < x:
add_to_top(val, count)
else:
add_to_rest(val, count)
result.append(top_sum)
# Sliding window
for i in range(k, n):
# Remove left element
left = nums[i - k]
old_count = freq[left]
freq[left] -= 1
new_count = freq[left]
# Rebuild heaps (simple approach for correctness)
top_heap.clear()
rest_heap.clear()
top_sum = 0
active_items = [(val, count) for val, count in freq.items() if count > 0]
active_items.sort(key=lambda x: (-x[1], -x[0]))
for j, (val, count) in enumerate(active_items):
if j < x:
add_to_top(val, count)
else:
add_to_rest(val, count)
# Add right element
right = nums[i]
freq[right] += 1
# Rebuild heaps again
top_heap.clear()
rest_heap.clear()
top_sum = 0
active_items = [(val, count) for val, count in freq.items() if count > 0]
active_items.sort(key=lambda x: (-x[1], -x[0]))
for j, (val, count) in enumerate(active_items):
if j < x:
add_to_top(val, count)
else:
add_to_rest(val, count)
result.append(top_sum)
return result
public class Solution {
public long[] FindXSum(int[] nums, int k, int x) {
var freq = new Dictionary<int, int>();
var result = new List<long>();
int n = nums.Length;
// Use SortedSet to maintain ordered elements
var topX = new SortedSet<(int count, int val)>();
var rest = new SortedSet<(int count, int val)>();
long topSum = 0;
void AddElement(int val, int count) {
var item = (count, val);
if (topX.Count < x) {
topX.Add(item);
topSum += (long)count * val;
} else {
var minTop = topX.Min;
if (item.CompareTo(minTop) > 0) {
topX.Remove(minTop);
topSum -= (long)minTop.count * minTop.val;
rest.Add(minTop);
topX.Add(item);
topSum += (long)count * val;
} else {
rest.Add(item);
}
}
}
void RemoveElement(int val, int count) {
var item = (count, val);
if (topX.Contains(item)) {
topX.Remove(item);
topSum -= (long)count * val;
if (rest.Count > 0) {
var maxRest = rest.Max;
rest.Remove(maxRest);
topX.Add(maxRest);
topSum += (long)maxRest.count * maxRest.val;
}
} else {
rest.Remove(item);
}
}
// Initialize first window
for (int i = 0; i < k; i++) {
freq[nums[i]] = freq.GetValueOrDefault(nums[i], 0) + 1;
}
foreach (var kvp in freq) {
AddElement(kvp.Key, kvp.Value);
}
result.Add(topSum);
// Sliding window
for (int i = k; i < n; i++) {
// Remove left element
int left = nums[i - k];
if (freq[left] > 0) {
RemoveElement(left, freq[left]);
freq[left]--;
if (freq[left] > 0) {
AddElement(left, freq[left]);
} else {
freq.Remove(left);
}
}
// Add right element
int right = nums[i];
if (freq.ContainsKey(right)) {
RemoveElement(right, freq[right]);
freq[right]++;
} else {
freq[right] = 1;
}
AddElement(right, freq[right]);
result.Add(topSum);
}
return result.ToArray();
}
}
var findXSum = function(nums, k, x) {
const n = nums.length;
const result = [];
for (let i = 0; i <= n - k; i++) {
const subarray = nums.slice(i, i + k);
const freq = new Map();
for (const num of subarray) {
freq.set(num, (freq.get(num) || 0) + 1);
}
const elements = Array.from(freq.entries());
elements.sort((a, b) => {
if (a[1] !== b[1]) return b[1] - a[1];
return b[0] - a[0];
});
let sum = 0;
const topX = Math.min(x, elements.length);
for (let j = 0; j < topX; j++) {
const [value, count] = elements[j];
sum += value * count;
}
result.push(sum);
}
return result;
};
复杂度分析
| 复杂度类型 | 复杂度 |
|---|---|
| 时间复杂度 | O(n * k * log k) |
| 空间复杂度 | O(k) |
说明：
- 时间复杂度：对于每个滑动窗口位置，需要维护有序集合，插入/删除操作为 O(log k)，窗口内最多有 k 个不同元素
- 空间复杂度：需要存储频次哈希表和两个有序集合，最多包含 k 个不同元素