class Solution {
public:
vector<long long> mostFrequentIDs(vector<int>& nums, vector<int>& freq) {
}
};
100258. 最高频率的 ID
你需要在一个集合里动态记录 ID 的出现频率。给你两个长度都为 n 的整数数组 nums 和 freq ，nums 中每一个元素表示一个 ID ，对应的 freq 中的元素表示这个 ID 在集合中此次操作后需要增加或者减少的数目。
freq[i] 是正数，那么 freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会添加到集合中。freq[i] 是负数，那么 -freq[i] 个 ID 为 nums[i] 的元素在第 i 步操作后会从集合中删除。请你返回一个长度为 n 的数组 ans ，其中 ans[i] 表示第 i 步操作后出现频率最高的 ID 数目 ，如果在某次操作后集合为空，那么 ans[i] 为 0 。
示例 1：
输入：nums = [2,3,2,1], freq = [3,2,-3,1]
输出：[3,3,2,2]
解释：
第 0 步操作后，有 3 个 ID 为 2 的元素，所以 ans[0] = 3 。
第 1 步操作后，有 3 个 ID 为 2 的元素和 2 个 ID 为 3 的元素，所以 ans[1] = 3 。
第 2 步操作后，有 2 个 ID 为 3 的元素，所以 ans[2] = 2 。
第 3 步操作后，有 2 个 ID 为 3 的元素和 1 个 ID 为 1 的元素，所以 ans[3] = 2 。
示例 2：
输入：nums = [5,5,3], freq = [2,-2,1]
输出：[2,0,1]
解释：
第 0 步操作后，有 2 个 ID 为 5 的元素，所以 ans[0] = 2 。
第 1 步操作后，集合中没有任何元素，所以 ans[1] = 0 。
第 2 步操作后，有 1 个 ID 为 3 的元素，所以 ans[2] = 1 。
提示：
1 <= nums.length == freq.length <= 1051 <= nums[i] <= 105-105 <= freq[i] <= 105freq[i] != 0原站题解
golang 解法, 执行用时: 276 ms, 内存消耗: 18.3 MB, 提交时间: 2024-03-24 23:03:22
// https://pkg.go.dev/github.com/emirpasic/gods/v2@v2.0.0-alpha
func mostFrequentIDs(nums, freq []int) []int64 {
cnt := map[int]int{}
t := redblacktree.New[int, int]()
ans := make([]int64, len(nums))
for i, x := range nums {
// 减少一次 cnt[x] 的出现次数
node := t.GetNode(cnt[x])
if node != nil {
node.Value--
if node.Value == 0 {
t.Remove(node.Key)
}
}
cnt[x] += freq[i]
// 增加一次 cnt[x] 的出现次数
node = t.GetNode(cnt[x])
if node == nil {
t.Put(cnt[x], 1)
} else {
node.Value++
}
ans[i] = int64(t.Right().Key)
}
return ans
}
golang 解法, 执行用时: 173 ms, 内存消耗: 19 MB, 提交时间: 2024-03-24 23:03:13
func mostFrequentIDs(nums, freq []int) []int64 {
ans := make([]int64, len(nums))
cnt := make(map[int]int)
h := hp{}
heap.Init(&h)
for i, x := range nums {
cnt[x] += freq[i]
heap.Push(&h, pair{cnt[x], x})
for h[0].c != cnt[h[0].x] { // 堆顶保存的数据已经发生变化
heap.Pop(&h) // 删除
}
ans[i] = int64(h[0].c)
}
return ans
}
type pair struct{ c, x int }
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].c > h[j].c } // 最大堆
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
java 解法, 执行用时: 169 ms, 内存消耗: 72.7 MB, 提交时间: 2024-03-24 23:02:48
class Solution {
public long[] mostFrequentIDs(int[] nums, int[] freq) {
Map<Integer, Long> cnt = new HashMap<>();
TreeMap<Long, Integer> m = new TreeMap<>();
int n = nums.length;
long[] ans = new long[n];
for (int i = 0; i < n; i++) {
int x = nums[i];
if (cnt.containsKey(x) && m.containsKey(cnt.get(x)) && m.merge(cnt.get(x), -1, Integer::sum) == 0) { // --m[cnt[x]] == 0
m.remove(cnt.get(x));
}
long c = cnt.merge(x, (long) freq[i], Long::sum); // cnt[x] += freq[i]
m.merge(c, 1, Integer::sum); // ++m[cnt[x]]
ans[i] = m.lastKey();
}
return ans;
}
public long[] mostFrequentIDs2(int[] nums, int[] freq) {
int n = nums.length;
long[] ans = new long[n];
Map<Integer, Long> cnt = new HashMap<>();
PriorityQueue<Pair<Long, Integer>> pq = new PriorityQueue<>((a, b) -> Long.compare(b.getKey(), a.getKey()));
for (int i = 0; i < n; i++) {
int x = nums[i];
long c = cnt.merge(x, (long) freq[i], Long::sum);
pq.add(new Pair<>(c, x));
while (!pq.peek().getKey().equals(cnt.get(pq.peek().getValue()))) { // 堆顶保存的数据已经发生变化
pq.poll(); // 删除
}
ans[i] = pq.peek().getKey();
}
return ans;
}
}
cpp 解法, 执行用时: 223 ms, 内存消耗: 149.4 MB, 提交时间: 2024-03-24 23:02:24
class Solution {
public:
vector<long long> mostFrequentIDs(vector<int> &nums, vector<int> &freq) {
int n = nums.size();
vector<long long> ans(n);
unordered_map<int, long long> cnt;
priority_queue<pair<long long, int>> pq;
for (int i = 0; i < n; i++) {
int x = nums[i];
cnt[x] += freq[i];
pq.emplace(cnt[x], x);
while (pq.top().first != cnt[pq.top().second]) { // 堆顶保存的数据已经发生变化
pq.pop(); // 删除
}
ans[i] = pq.top().first;
}
return ans;
}
vector<long long> mostFrequentIDs2(vector<int> &nums, vector<int> &freq) {
unordered_map<int, long long> cnt;
multiset<long long> m;
int n = nums.size();
vector<long long> ans(n);
for (int i = 0; i < n; i++) {
int x = nums[i];
auto it = m.find(cnt[x]);
if (it != m.end()) {
m.erase(it);
}
cnt[x] += freq[i];
m.insert(cnt[x]);
ans[i] = *m.rbegin();
}
return ans;
}
};
python3 解法, 执行用时: 849 ms, 内存消耗: 40.4 MB, 提交时间: 2024-03-24 23:01:55
from sortedcontainers import SortedList
class Solution:
def mostFrequentIDs(self, nums: List[int], freq: List[int]) -> List[int]:
cnt = Counter()
sl = SortedList()
ans = []
for x, f in zip(nums, freq):
if cnt[x] in sl:
sl.remove(cnt[x]) # 多个 cnt[x] 只会移除一个
cnt[x] += f
sl.add(cnt[x])
ans.append(sl[-1])
return ans
def mostFrequentIDs2(self, nums: List[int], freq: List[int]) -> List[int]:
ans = []
cnt = Counter()
h = []
for x, f in zip(nums, freq):
cnt[x] += f
heappush(h, (-cnt[x], x)) # 取负号变成最大堆
while -h[0][0] != cnt[h[0][1]]: # 堆顶保存的数据已经发生变化
heappop(h) # 删除
ans.append(-h[0][0])
return ans