题目
在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。
给你一个整数数组 arr，请你从中找出并返回一个幸运数。
如果数组中存在多个幸运数，只需返回 最大 的那个。 如果数组中不含幸运数，则返回 -1 。
题干
整数的出现频次和它的数值大小相等
找出并返回一个幸运数
思路
整数的出现频次和它的数值大小相等 即有可能有多个重复数字
重复数字有什么特性
找出并返回一个幸运数 涉及到查找算法
哈希表
通过遍历数组 将数字存储在哈希表中 key为数字 value为出现次数
在循环遍历map 找到最大的幸运数字接口
数组
通过遍历数组 将数组下标作为值存储 数组的值为出现的次数
最后从数组从大到小取值即可
位运算
解答
数组
public class Solution {
public int findLucky(int[] arr) {
int[] freq = new int[501];
for (int i = 0; i < arr.length; i++) {
freq[arr[i]]++;
}
for (int i = 500; i > 0; i--) {
if (freq[i] == i) {
return i;
}
}
return -1;
}
}
哈希表
class Solution {
public int findLucky(int[] arr) {
HashMap<Integer,Integer> map= new HashMap();
for(int i=0;i<arr.length;i++){
int num = arr[i];
Integer appearNum = map.get(num);
if(appearNum==null){
map.put(num,1);
}else{
map.put(num,appearNum+1);
}
}
int nowSameValue = -1;
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
if(entry.getKey()==entry.getValue()){
if(entry.getKey()>nowSameValue){
nowSameValue = entry.getKey();
}
}
}
return nowSameValue;
}
}
时空复杂度分析
如果采用哈希表解法 时间复杂度为O(n) 空间复杂度为O(n)
如果采用数组解法 时间复杂度为O(n) 空间复杂度为O(n) 虽然是一个量级 数组解法更简单更快
结语
此题涉及到对空间的运用 善用空间能有效的提高我们的查询速度
