1394. 找出数组中的幸运数

🟢   🔖  数组 哈希表 计数  🔗 力扣 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; // 返回结果
};