Rust）

2025年7月3日 13:37

方法一：哈希表

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

然后遍历哈希表，其中 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}$ 等长的数组，表示每次操作后的答案。

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

分类题单

如何科学刷题？

我的题解精选（已分类）

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

阅读视图

方法一：哈希表

复杂度分析

方法二：数组

复杂度分析

思考题

分类题单