寻找幸运数

算法

Posted by CH on May 18, 2020

题目

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

给你一个整数数组 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) 虽然是一个量级 数组解法更简单更快

结语

此题涉及到对空间的运用 善用空间能有效的提高我们的查询速度