最高频率的 ID
难度:
标签:
题目描述
The problem involves tracking the frequency of IDs in a collection that changes over time. You have two integer arrays, nums and freq, of equal length n. Each element in nums represents an ID, and the corresponding element in freq indicates how many times that ID should be added to or removed from the collection at each step.
- Addition of IDs: If
freq[i]is positive, it meansfreq[i]IDs with the valuenums[i]are added to the collection at stepi. - Removal of IDs: If
freq[i]is negative, it means-freq[i]IDs with the valuenums[i]are removed from the collection at stepi.
Return an array ans of length n, where ans[i] represents the count of the most frequent ID in the collection after the ith step. If the collection is empty at any step, ans[i] should be 0 for that step.
Example 1:
Input: nums = [2,3,2,1], freq = [3,2,-3,1]
Output: [3,3,2,2]
Explanation:
After step 0, we have 3 IDs with the value of 2. So ans[0] = 3.
After step 1, we have 3 IDs with the value of 2 and 2 IDs with the value of 3. So ans[1] = 3.
After step 2, we have 2 IDs with the value of 3. So ans[2] = 2.
After step 3, we have 2 IDs with the value of 3 and 1 ID with the value of 1. So ans[3] = 2.
Example 2:
Input: nums = [5,5,3], freq = [2,-2,1]
Output: [2,0,1]
Explanation:
After step 0, we have 2 IDs with the value of 5. So ans[0] = 2.
After step 1, there are no IDs. So ans[1] = 0.
After step 2, we have 1 ID with the value of 3. So ans[2] = 1.
Constraints:
1 <= nums.length == freq.length <= 1051 <= nums[i] <= 105-105 <= freq[i] <= 105freq[i] != 0- The input is generated such that the occurrences of an ID will not be negative in any step.
代码结果
运行时间: 244 ms, 内存: 37.0 MB
// Solution in Java using Streams
// The approach remains the same as the Java solution but utilizing Streams for certain operations.
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
import java.util.stream.IntStream;
public class FrequencyTrackerStream {
public int[] findMaxFrequencies(int[] nums, int[] freq) {
int n = nums.length;
int[] ans = new int[n];
Map<Integer, Integer> idToFreq = new HashMap<>();
TreeMap<Integer, Integer> freqCount = new TreeMap<>();
IntStream.range(0, n).forEach(i -> {
int id = nums[i];
int change = freq[i];
// Update the frequency in the map
int oldFreq = idToFreq.getOrDefault(id, 0);
int newFreq = oldFreq + change;
idToFreq.put(id, newFreq);
// Update the frequency count map
if (oldFreq > 0) {
freqCount.put(oldFreq, freqCount.get(oldFreq) - 1);
if (freqCount.get(oldFreq) == 0) freqCount.remove(oldFreq);
}
freqCount.put(newFreq, freqCount.getOrDefault(newFreq, 0) + 1);
// Get the maximum frequency
ans[i] = freqCount.isEmpty() ? 0 : freqCount.lastKey();
});
return ans;
}
}
解释
方法:
时间复杂度:
空间复杂度: