LeetCode 2190: Most Frequent Number Following Key (One Pass Frequency Counting)
LeetCode 2190ArrayCountingToday we solve LeetCode 2190 - Most Frequent Number Following Key.
Source: https://leetcode.com/problems/most-frequent-number-following-key/
English
Problem Summary
Given an integer array nums and an integer key, each time nums[i] == key we collect the next value nums[i+1]. Return the value that appears most frequently among those collected targets.
Key Insight
Only adjacent pairs matter. We scan once from left to right, and when we hit key at index i, we increment the frequency of nums[i+1]. Track the current best target while counting.
Algorithm
- Create a frequency map freq.
- Initialize bestTarget = -1, bestCount = 0.
- For each i in [0, n-2]: if nums[i] == key, let t = nums[i+1], then freq[t]++.
- If freq[t] > bestCount, update bestCount and bestTarget.
- Return bestTarget.
Complexity Analysis
Time: O(n).
Space: O(k), where k is number of distinct targets after key.
Common Pitfalls
- Iterating to n-1 and reading nums[i+1] out of bounds.
- Counting all values instead of only values immediately after key.
- Forgetting to update answer as frequencies increase.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int mostFrequent(int[] nums, int key) {
Map<Integer, Integer> freq = new HashMap<>();
int bestTarget = -1;
int bestCount = 0;
for (int i = 0; i + 1 < nums.length; i++) {
if (nums[i] == key) {
int t = nums[i + 1];
int c = freq.getOrDefault(t, 0) + 1;
freq.put(t, c);
if (c > bestCount) {
bestCount = c;
bestTarget = t;
}
}
}
return bestTarget;
}
}func mostFrequent(nums []int, key int) int {
freq := map[int]int{}
bestTarget, bestCount := -1, 0
for i := 0; i+1 < len(nums); i++ {
if nums[i] == key {
t := nums[i+1]
freq[t]++
if freq[t] > bestCount {
bestCount = freq[t]
bestTarget = t
}
}
}
return bestTarget
}class Solution {
public:
int mostFrequent(vector<int>& nums, int key) {
unordered_map<int, int> freq;
int bestTarget = -1, bestCount = 0;
for (int i = 0; i + 1 < (int)nums.size(); ++i) {
if (nums[i] == key) {
int t = nums[i + 1];
int c = ++freq[t];
if (c > bestCount) {
bestCount = c;
bestTarget = t;
}
}
}
return bestTarget;
}
};class Solution:
def mostFrequent(self, nums: List[int], key: int) -> int:
freq = {}
best_target = -1
best_count = 0
for i in range(len(nums) - 1):
if nums[i] == key:
t = nums[i + 1]
freq[t] = freq.get(t, 0) + 1
if freq[t] > best_count:
best_count = freq[t]
best_target = t
return best_targetvar mostFrequent = function(nums, key) {
const freq = new Map();
let bestTarget = -1;
let bestCount = 0;
for (let i = 0; i + 1 < nums.length; i++) {
if (nums[i] === key) {
const t = nums[i + 1];
const c = (freq.get(t) || 0) + 1;
freq.set(t, c);
if (c > bestCount) {
bestCount = c;
bestTarget = t;
}
}
}
return bestTarget;
};中文
题目概述
给定整数数组 nums 和整数 key。每当出现 nums[i] == key 时，就把后一个数 nums[i+1] 记为目标值。返回这些目标值中出现次数最多的那个。
核心思路
只需要关注相邻位置。线性扫描数组，当发现 nums[i] == key，就对 nums[i+1] 做一次计数；同时维护当前出现次数最多的目标值。
算法步骤
- 使用哈希表 freq 记录目标值频次。
- 初始化 bestTarget = -1、bestCount = 0。
- 遍历 i = 0..n-2：若 nums[i] == key，令 t = nums[i+1]，然后 freq[t]++。
- 若 freq[t] > bestCount，更新答案。
- 遍历结束返回 bestTarget。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(k)，其中 k 是出现在 key 后面的不同数字个数。
常见陷阱
- 循环写到 n-1 导致访问 nums[i+1] 越界。
- 误把整个数组计数，而不是只统计紧跟在 key 后的数字。
- 计数增长后忘记同步更新当前最优答案。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int mostFrequent(int[] nums, int key) {
Map<Integer, Integer> freq = new HashMap<>();
int bestTarget = -1;
int bestCount = 0;
for (int i = 0; i + 1 < nums.length; i++) {
if (nums[i] == key) {
int t = nums[i + 1];
int c = freq.getOrDefault(t, 0) + 1;
freq.put(t, c);
if (c > bestCount) {
bestCount = c;
bestTarget = t;
}
}
}
return bestTarget;
}
}func mostFrequent(nums []int, key int) int {
freq := map[int]int{}
bestTarget, bestCount := -1, 0
for i := 0; i+1 < len(nums); i++ {
if nums[i] == key {
t := nums[i+1]
freq[t]++
if freq[t] > bestCount {
bestCount = freq[t]
bestTarget = t
}
}
}
return bestTarget
}class Solution {
public:
int mostFrequent(vector<int>& nums, int key) {
unordered_map<int, int> freq;
int bestTarget = -1, bestCount = 0;
for (int i = 0; i + 1 < (int)nums.size(); ++i) {
if (nums[i] == key) {
int t = nums[i + 1];
int c = ++freq[t];
if (c > bestCount) {
bestCount = c;
bestTarget = t;
}
}
}
return bestTarget;
}
};class Solution:
def mostFrequent(self, nums: List[int], key: int) -> int:
freq = {}
best_target = -1
best_count = 0
for i in range(len(nums) - 1):
if nums[i] == key:
t = nums[i + 1]
freq[t] = freq.get(t, 0) + 1
if freq[t] > best_count:
best_count = freq[t]
best_target = t
return best_targetvar mostFrequent = function(nums, key) {
const freq = new Map();
let bestTarget = -1;
let bestCount = 0;
for (let i = 0; i + 1 < nums.length; i++) {
if (nums[i] === key) {
const t = nums[i + 1];
const c = (freq.get(t) || 0) + 1;
freq.set(t, c);
if (c > bestCount) {
bestCount = c;
bestTarget = t;
}
}
}
return bestTarget;
};
Comments