哈希表题目：找出数组中的幸运数
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
文章目录
题目
标题和出处
标题找出数组中的幸运数
难度
3 级
题目描述
要求
给定一个整数数组 arr \texttt{arr} arr幸运数是在数组中的出现频次和数值相等的整数。
返回数组中的一个幸运数。如果存在多个幸运数返回最大的那个。如果没有幸运数返回 -1 \texttt{-1} -1。
示例
示例 1
输入
arr
=
[2,2,3,4]
\texttt{arr = [2,2,3,4]}
arr = [2,2,3,4]
输出
2
\texttt{2}
2
解释数组中唯一的幸运数是
2
\texttt{2}
2因为数值
2
\texttt{2}
2 的出现频次也是
2
\texttt{2}
2。
示例 2
输入
arr
=
[1,2,2,3,3,3]
\texttt{arr = [1,2,2,3,3,3]}
arr = [1,2,2,3,3,3]
输出
3
\texttt{3}
3
解释
1
\texttt{1}
1、
2
\texttt{2}
2 以及
3
\texttt{3}
3 都是幸运数只需要返回其中最大的数。
示例 3
输入
arr
=
[2,2,2,3,3]
\texttt{arr = [2,2,2,3,3]}
arr = [2,2,2,3,3]
输出
-1
\texttt{-1}
-1
解释数组中不存在幸运数。
示例 4
输入
arr
=
[5]
\texttt{arr = [5]}
arr = [5]
输出
-1
\texttt{-1}
-1
示例 5
输入
arr
=
[7,7,7,7,7,7,7]
\texttt{arr = [7,7,7,7,7,7,7]}
arr = [7,7,7,7,7,7,7]
输出
7
\texttt{7}
7
数据范围
- 1 ≤ arr.length ≤ 500 \texttt{1} \le \texttt{arr.length} \le \texttt{500} 1≤arr.length≤500
- 1 ≤ arr[i] ≤ 500 \texttt{1} \le \texttt{arr[i]} \le \texttt{500} 1≤arr[i]≤500
解法
思路和算法
为了寻找数组中的幸运数需要遍历数组统计每个整数的出现频次然后寻找出现频次和数值相等的整数并返回其中最大的数。
由于数组中的每个整数的出现频次一定是正整数且数组中的每个元素都是正整数因此如果幸运数存在幸运数一定是正整数。
首先遍历数组并使用哈希表记录每个整数的出现频次。得到每个整数的出现频次之后将幸运数初始化为 − 1 -1 −1遍历哈希表寻找最大的幸运数。哈希表中的键对应整数值对应频次对于哈希表中的每个键值对如果键和值相等则遇到一个幸运数用该幸运数更新最大幸运数。遍历哈希表结束之后返回幸运数。
上述做法对于数组中存在幸运数和不存在幸运数的情况都能得到正确的结果
-
如果数组中存在幸运数由于幸运数一定大于 − 1 -1 −1每次都维护最大的幸运数因此遍历哈希表结束之后可以得到最大的幸运数
-
如果数组中不存在幸运数则幸运数的值不会被更新遍历哈希表结束之后幸运数的值还是 − 1 -1 −1。
代码
class Solution {
public int findLucky(int[] arr) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : arr) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
int lucky = -1;
Set<Integer> set = map.keySet();
for (int num : set) {
if (num == map.get(num)) {
lucky = Math.max(lucky, num);
}
}
return lucky;
}
}
复杂度分析
-
时间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组 arr \textit{arr} arr 的长度。需要遍历数组一次使用哈希表记录每个整数的出现频次然后遍历哈希表寻找最大的幸运数由于哈希表中的键值对个数不超过 n n n因此时间复杂度是 O ( n ) O(n) O(n)。
-
空间复杂度 O ( n ) O(n) O(n)其中 n n n 是数组 arr \textit{arr} arr 的长度。空间复杂度主要取决于哈希表哈希表中的键值对个数不超过 n n n。