跳至主要內容

2190. 数组中紧跟 key 之后出现最频繁的数字

2190. 数组中紧跟 key 之后出现最频繁的数字

🟢   🔖  数组 哈希表 计数  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given a 0-indexed integer array nums. You are also given an integer key, which is present in nums.

For every unique integer target in nums, count the number of times target immediately follows an occurrence of key in nums. In other words, count the number of indices i such that:

  • 0 <= i <= nums.length - 2,
  • nums[i] == key and,
  • nums[i + 1] == target.

Return thetarget with themaximum count. The test cases will be generated such that the target with maximum count is unique.

Example 1:

Input: nums = [1,100,200,1,100], key = 1

Output: 100

Explanation: For target = 100, there are 2 occurrences at indices 1 and 4 which follow an occurrence of key.

No other integers follow an occurrence of key, so we return 100.

Example 2:

Input: nums = [2,2,2,2,3], key = 2

Output: 2

Explanation: For target = 2, there are 3 occurrences at indices 1, 2, and 3 which follow an occurrence of key.

For target = 3, there is only one occurrence at index 4 which follows an occurrence of key.

target = 2 has the maximum number of occurrences following an occurrence of key, so we return 2.

Constraints:

  • 2 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • The test cases will be generated such that the answer is unique.

题目大意

给你一个下标从 0 开始的整数数组 nums ，同时给你一个整数 key ，它在 nums 出现过。

统计 在 nums 数组中紧跟着 key 后面出现的不同整数 target 的出现次数。换言之，target 的出现次数为满足以下条件的 i 的数目：

  • 0 <= i <= n - 2
  • nums[i] == key 且
  • nums[i + 1] == target 。

请你返回出现 最多 次数的 target 。测试数据保证出现次数最多的 target 是唯一的。

示例 1：

输入： nums = [1,100,200,1,100], key = 1

输出： 100

解释： 对于 target = 100 ，在下标 1 和 4 处出现过 2 次，且都紧跟着 key 。

没有其他整数在 key 后面紧跟着出现，所以我们返回 100 。

示例 2：

输入： nums = [2,2,2,2,3], key = 2

输出： 2

解释： 对于 target = 2 ，在下标 1 ，2 和 3 处出现过 3 次，且都紧跟着 key 。

对于 target = 3 ，在下标 4 出出现过 1 次，且紧跟着 key 。

target = 2 是紧跟着 key 之后出现次数最多的数字，所以我们返回 2 。

提示：

  • 2 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • 测试数据保证答案是唯一的。

解题思路

  1. 遍历数组 nums，当 nums[i] 等于 key 时，记录 nums[i + 1] 的出现次数。
  2. 使用 Map 数据结构存储数字及其对应的出现频率。
  3. 遍历 Map，找出出现次数最多的数字。

复杂度分析

  • 时间复杂度：O(n + m)
    • 遍历数组的时间复杂度：O(n)，其中 n 是数组的长度。
    • 遍历 Map 的时间复杂度：O(m)，其中 m 是紧随 key 之后的唯一数字的个数。
    • 总时间复杂度：O(n + m)。
  • 空间复杂度：O(m)，使用了 Map 存储紧随 key 之后数字的频率，其中 m 是不同数字的个数。

代码

/**
 * @param {number[]} nums
 * @param {number} key
 * @return {number}
 */
var mostFrequent = function (nums, key) {
	let freq = new Map(); // 用于记录数字及其出现的频率

	// 统计紧随 key 之后数字的频率
	for (let i = 0; i < nums.length - 1; i++) {
		if (nums[i] == key) {
			// 如果当前数字等于 key
			freq.set(nums[i + 1], (freq.get(nums[i + 1]) || 0) + 1); // 更新频率
		}
	}

	// 找出频率最大的数字
	let maxFreq = 0,
		res;
	for (let [num, val] of freq.entries()) {
		// 遍历 Map
		if (val > maxFreq) {
			// 如果当前频率大于最大频率
			maxFreq = val; // 更新最大频率
			res = num; // 更新结果
		}
	}

	return res; // 返回出现频率最高的数字
};

相关题目

题号标题题解标签难度力扣
1636按照频率将数组升序排序[✓]数组 哈希表 排序🟢🀄️open in new window 🔗open in new window