CTF of Z2BNS
0%

找出数组中的幸运数

发表于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 837 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

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

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

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

示例1：

1
2
3
输入：arr = [2,2,3,4]
输出：2
解释：数组中唯一的幸运数是 2 ，因为数值 2 的出现频次也是 2 。

示例2：

1
2
3
输入：arr = [1,2,2,3,3,3]
输出：3
解释：1、2 以及 3 都是幸运数，只需要返回其中最大的 3 。

示例3：

1
2
3
输入：arr = [2,2,2,3,3]
输出：-1
解释：数组中不存在幸运数。

示例4：

1
2
输入：arr = [5]
输出：-1

示例5：

1
2
输入：arr = [7,7,7,7,7,7,7]
输出：7

提示：

  • 1 <= arr.length <= 500
  • 1 <= arr[i] <= 500
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

统计数组中整数出现的频次存到map集合中，然后遍历map集合返回最大的那个幸运数。

c++代码：(执行用时12ms，击败87.94%，内存消耗10.5M，击败20.56%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findLucky(vector<int>& arr) {
        unordered_map<int,int> m;
        int result=-1;
        for(int i:arr){
            ++m[i];
        }
        for(auto [j,k]:m){
            if(j==k){
                result=j>result?j:result;
            }
        }
        return result;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一：哈希映射
思路

我们可以使用哈希映射来解决这个问题，把数值作为键，把数值出现的次数作为值。具体地，我们先遍历原数组建立哈希表，然后遍历哈希表找到最大的键和值相等的元素作为答案，如果找不到就返回 -1。

fig1

c++代码：(执行用时12ms，击败87.94%，内存消耗10.5M，击败20.56%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    unordered_map <int, int> m;
    int findLucky(vector<int>& arr) {
        for (auto x: arr) ++m[x];
        int ans = -1;
        for (auto [key, value]: m) {
            if (key == value) {
                ans = max(ans, key);
            }
        }
        return ans;
    }
};

复杂度分析

记数组中的的元素个数为 $n$，则哈希表中最多有 $n$ 个键值对。

  • 时间复杂度：遍历数组的时间代价是 $O(n)$，遍历哈希表的时间代价也是 $O(n)$，故渐进时间复杂度 $O(n)$。

  • 空间复杂度：哈希表中最多有 $n$ 个键值对，故渐进空间复杂度 $O(n)$。

⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

哈希映射计数法，简单题。

------------- THE END! THANKS! -------------