1394.md

title	description	keywords
1394. 找出数组中的幸运数	LeetCode 1394. 找出数组中的幸运数题解，Find Lucky Integer in an Array，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1394. 找出数组中的幸运数 找出数组中的幸运数 Find Lucky Integer in an Array 解题思路 数组 哈希表 计数

1394. 找出数组中的幸运数

🟢 Easy  🔖  数组 哈希表 计数  🔗 力扣 LeetCode

题目

Given an array of integers arr, a lucky integer is an integer that has a frequency in the array equal to its value.

Return the largest lucky integer in the array. If there is no lucky integer return -1.

Example 1:

Input: arr = [2,2,3,4]

Output: 2

Explanation: The only lucky number in the array is 2 because frequency[2] == 2.

Example 2:

Input: arr = [1,2,2,3,3,3]

Output: 3

Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.

Example 3:

Input: arr = [2,2,2,3,3]

Output: -1

Explanation: There are no lucky numbers in the array.

Constraints:

• 1 <= arr.length <= 500
• 1 <= arr[i] <= 500

题目大意

在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。

给你一个整数数组 arr，请你从中找出并返回一个幸运数。

• 如果数组中存在多个幸运数，只需返回 最大 的那个。
• 如果数组中不含幸运数，则返回 -1 。

示例 1：

输入： arr = [2,2,3,4]

输出： 2

解释： 数组中唯一的幸运数是 2 ，因为数值 2 的出现频次也是 2 。

示例 2：

输入： arr = [1,2,2,3,3,3]

输出： 3

解释： 1、2 以及 3 都是幸运数，只需要返回其中最大的 3 。

示例 3：

输入： arr = [2,2,2,3,3]

输出： -1

解释： 数组中不存在幸运数。

示例 4：

输入： arr = [5]

输出： -1

示例 5：

输入： arr = [7,7,7,7,7,7,7]

输出： 7

提示：

• 1 <= arr.length <= 500
• 1 <= arr[i] <= 500

解题思路

1. 统计数组中的每个数的出现次数
   使用一个对象 count，记录数组中每个数字出现的次数。

   • 遍历数组 arr，对每个数字 num，将其出现次数累加到 count[num] 中。

2. 查找「幸运整数」
   使用 for in 遍历对象 count 的键值对，key 会从小到大被遍历到：

   • 如果键 key 等于其值 count[key]，说明这是一个「幸运整数」。
   • 更新当前找到的最大「幸运整数」。

3. 返回结果

   • 如果找到至少一个「幸运整数」，返回最大值。
   • 否则返回 -1。

复杂度分析

• 时间复杂度：O(n)

  • 统计次数：遍历数组 arr 一次，时间复杂度为 O(n)，其中 n 是数组长度。
  • 查找幸运整数：遍历哈希表，时间复杂度为 O(k)，其中 k 是数组中不同元素的数量。
  • 总时间复杂度：O(n)，因为 k <= n。

• 空间复杂度：O(k)，使用了一个哈希表 count 存储数组中不同数字的出现次数。

代码

/**
 * @param {number[]} arr
 * @return {number}
 */
var findLucky = function (arr) {
	let count = {}; // 哈希表用于统计出现次数
	for (let num of arr) {
		if (!count[num]) {
			count[num] = 0;
		}
		count[num]++;
	}

	let lucky = -1; // 初始值为 -1 表示不存在幸运整数
	for (let key in count) {
		if (key == count[key]) {
			// 检查是否是幸运整数
			lucky = Math.max(lucky, count[key]); // 更新最大幸运整数
		}
	}
	return lucky; // 返回结果
};