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

给你一个整数数组 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

方法一：哈希表

用哈希表统计每个元素的出现次数。

然后遍历哈希表，其中 key 等于 value 的元素即为幸运数，取其最大值。如果不存在这样的元素，答案为 $-1$。

###py

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        cnt = Counter(arr)
        ans = -1
        for x, c in cnt.items():
            if x == c:
                ans = max(ans, x)
        return ans

###py

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        cnt = Counter(arr)
        return max((x for x, c in cnt.items() if x == c), default=-1) 

###java

class Solution {
    public int findLucky(int[] arr) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : arr) {
            cnt.merge(x, 1, Integer::sum);
        }

        int ans = -1;
        for (Map.Entry<Integer, Integer> e : cnt.entrySet()) {
            int x = e.getKey();
            int c = e.getValue();
            if (x == c) {
                ans = Math.max(ans, x);
            }
        }
        return ans;
    }
}

###cpp

class Solution {
public:
    int findLucky(vector<int>& arr) {
        unordered_map<int, int> cnt;
        for (int x : arr) {
            cnt[x]++;
        }

        int ans = -1;
        for (auto& [x, c] : cnt) {
            if (x == c) {
                ans = max(ans, x);
            }
        }
        return ans;
    }
};

###go

func findLucky(arr []int) int {
cnt := map[int]int{}
for _, x := range arr {
cnt[x]++
}

ans := -1
for x, c := range cnt {
if x == c {
ans = max(ans, x)
}
}
return ans
}

###js

var findLucky = function(arr) {
    const cnt = new Map();
    for (const x of arr) {
        cnt.set(x, (cnt.get(x) ?? 0) + 1);
    }

    let ans = -1;
    for (const [x, c] of cnt.entries()) {
        if (x === c) {
            ans = Math.max(ans, x);
        }
    }
    return ans;
};

###rust

use std::collections::HashMap;

impl Solution {
    pub fn find_lucky(arr: Vec<i32>) -> i32 {
        let mut cnt = HashMap::new();
        for x in arr {
            *cnt.entry(x).or_insert(0) += 1;
        }

        let mut ans = -1;
        for (x, c) in cnt {
            if x == c {
                ans = ans.max(x);
            }
        }
        ans
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

方法二：数组

由于一个数的出现次数不可能大于 $n$，所以大于 $n$ 的元素一定不是幸运数。我们只需统计 $\le n$ 的元素出现次数。

所以只需创建一个大小为 $n+1$ 的 $\textit{cnt}$ 数组统计。

###py

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        n = len(arr)
        cnt = [0] * (n + 1)
        for x in arr:
            if x <= n:
                cnt[x] += 1

        for i in range(n, 0, -1):
            if cnt[i] == i:
                return i
        return -1

###java

class Solution {
    public int findLucky(int[] arr) {
        int n = arr.length;
        int[] cnt = new int[n + 1];
        for (int x : arr) {
            if (x <= n) {
                cnt[x]++;
            }
        }

        for (int i = n; i > 0; i--) {
            if (cnt[i] == i) {
                return i;
            }
        }
        return -1;
    }
}

###cpp

class Solution {
public:
    int findLucky(vector<int>& arr) {
        int n = arr.size();
        vector<int> cnt(n + 1);
        for (int x : arr) {
            if (x <= n) {
                cnt[x]++;
            }
        }

        for (int i = n; i > 0; i--) {
            if (cnt[i] == i) {
                return i;
            }
        }
        return -1;
    }
};

###c

int findLucky(int* arr, int arrSize) {
    int* cnt = calloc(arrSize + 1, sizeof(int));
    for (int i = 0; i < arrSize; i++) {
        if (arr[i] <= arrSize) {
            cnt[arr[i]]++;
        }
    }

    for (int i = arrSize; i > 0; i--) {
        if (cnt[i] == i) {
            free(cnt);
            return i;
        }
    }
    free(cnt);
    return -1;
}

###go

func findLucky(arr []int) int {
n := len(arr)
cnt := make([]int, n+1)
for _, x := range arr {
if x <= n {
cnt[x]++
}
}

for i := n; i >= 1; i-- {
if cnt[i] == i {
return i
}
}
return -1
}

###js

var findLucky = function(arr) {
    const n = arr.length;
    const cnt = Array(n + 1).fill(0);
    for (const x of arr) {
        if (x <= n) {
            cnt[x]++;
        }
    }

    for (let i = n; i > 0; i--) {
        if (cnt[i] === i) {
            return i;
        }
    }
    return -1;
};

###rust

impl Solution {
    pub fn find_lucky(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let mut cnt = vec![0; n + 1];
        for x in arr {
            if x as usize <= n {
                cnt[x as usize] += 1;
            }
        }

        for i in (1..=n).rev() {
            if cnt[i] as usize == i {
                return i as _;
            }
        }
        -1
    }
}

复杂度分析

• 时间复杂度：$\mathcal{O}(n)$，其中 $n$ 是 $\textit{nums}$ 的长度。
• 空间复杂度：$\mathcal{O}(n)$。

思考题

动态地往 $\textit{arr}$ 中添加、删除元素，每次操作后，输出最大幸运数（不存在则为 $-1$）。

具体来说，额外输入一个 $\textit{queries}$ 数组，其中 $\textit{queries}[i] = [\textit{op}, x]$，如果 $\textit{op}=1$ 表示往 $\textit{arr}$ 中添加一个 $x$；如果 $\textit{op}=2$ 表示删除 $\textit{arr}$ 中的一个 $x$。你需要返回一个与 $\textit{queries}$ 等长的数组，表示每次操作后的答案。

欢迎在评论区分享你的思路/代码。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/基环树/最短路/最小生成树/网络流）
7. 动态规划（入门/背包/划分/状态机/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

计数器法,然后倒叙便利计数器中的值, 若下标的值 == 出现的次数, 则直接返回即可(此时即为最大值)

class Solution {
    public int findLucky(int[] arr) {
        int[] temp = new int[501];
        // 将出现次数存入计数器
        for (int i : arr) {
            temp[i]++;
        }

        // 倒叙便利计数器中的值, 若下标的值 == 出现的次数, 则直接返回即可(此时即为最大值)
        for (int i = temp.length - 1; i >= 1; i--) {
            if (i == temp[i]) {
                return i;
            }
        }

        // 说明没有幸运数
        return -1;
    }
}

方法一：哈希映射

思路

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

代码

###C++

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;
    }
};

###Python

class Solution:
    def findLucky(self, arr: List[int]) -> int:
        m = dict()
        for x in arr:
            m[x] = m.get(x, 0) + 1
        ans = -1
        for (key, value) in m.items():
            if key == value:
                ans = max(ans, key)
        return ans

###Java

class Solution {
    public int findLucky(int[] arr) {
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        for (int x : arr) {
            m.put(x, m.getOrDefault(x, 0) + 1);
        }
        int ans = -1;
        for (Map.Entry<Integer, Integer> entry : m.entrySet()) {
            int key = entry.getKey(), value = entry.getValue();
            if (key == value) {
                ans = Math.max(ans, key);
            }
        }
        return ans;
    }
}

###C#

public class Solution {
    public int FindLucky(int[] arr) {
        Dictionary<int, int> m = new Dictionary<int, int>();
        foreach (int x in arr) {
            if (m.ContainsKey(x)) {
                m[x]++;
            } else {
                m[x] = 1;
            }
        }
        int ans = -1;
        foreach (var kvp in m) {
            if (kvp.Key == kvp.Value) {
                ans = Math.Max(ans, kvp.Key);
            }
        }
        return ans;
    }
}

###Go

func findLucky(arr []int) int {
    m := make(map[int]int)
    for _, x := range arr {
        m[x]++
    }
    ans := -1
    for key, value := range m {
        if key == value {
            ans = max(ans, key)
        }
    }
    return ans
}

###C

typedef struct {
    int key;
    int val;
    UT_hash_handle hh;
} HashItem; 

HashItem *hashFindItem(HashItem **obj, int key) {
    HashItem *pEntry = NULL;
    HASH_FIND_INT(*obj, &key, pEntry);
    return pEntry;
}

bool hashAddItem(HashItem **obj, int key, int val) {
    if (hashFindItem(obj, key)) {
        return false;
    }
    HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
    pEntry->key = key;
    pEntry->val = val;
    HASH_ADD_INT(*obj, key, pEntry);
    return true;
}

bool hashSetItem(HashItem **obj, int key, int val) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        hashAddItem(obj, key, val);
    } else {
        pEntry->val = val;
    }
    return true;
}

int hashGetItem(HashItem **obj, int key, int defaultVal) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        return defaultVal;
    }
    return pEntry->val;
}

void hashFree(HashItem **obj) {
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);  
        free(curr);
    }
}

int findLucky(int* arr, int arrSize) {
    HashItem *m = NULL;
    for (int i = 0; i < arrSize; i++) {
        hashSetItem(&m, arr[i], hashGetItem(&m, arr[i], 0) + 1);
    }
    int ans = -1;
    for (HashItem *pEntry = m; pEntry; pEntry = pEntry->hh.next) {
        if (pEntry->key == pEntry->val) {
            ans = fmax(ans, pEntry->key);
        }
    }
    hashFree(&m);
    return ans;
}

###JavaScript

var findLucky = function(arr) {
    let m = {}
    arr.forEach((x) => {
        m[x] = (x in m ? m[x] + 1 : 1)
    })
    let ans = -1
    Object.keys(m).forEach((key) => {
        ans = (key == m[key] ? Math.max(key, ans) : ans)
    })
    return ans
};

###TypeScript

function findLucky(arr: number[]): number {
    const m = new Map<number, number>();
    for (const x of arr) {
        m.set(x, (m.get(x) || 0) + 1);
    }
    let ans = -1;
    for (const [key, value] of m) {
        if (key === value) {
            ans = Math.max(ans, key);
        }
    }
    return ans;
};

###Rust

use std::collections::HashMap;

impl Solution {
    pub fn find_lucky(arr: Vec<i32>) -> i32 {
        let mut m = HashMap::new();
        for x in arr {
            *m.entry(x).or_insert(0) += 1;
        }
        let mut ans = -1;
        for (&key, &value) in m.iter() {
            if key == value {
                ans = ans.max(key);
            }
        }
        ans
    }
}

复杂度分析

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

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

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