Description
Given an array of integers arr, a lucky integer is an integer that has a frequency in the array equal to its value.
Return the largest lucky integer in the array. If there is no lucky integer return -1.
Example 1:
Input: arr = [2,2,3,4]
Output: 2
Explanation: The only lucky number in the array is 2 because frequency[2] == 2.
Example 2:
Input: arr = [1,2,2,3,3,3]
Output: 3
Explanation: 1, 2 and 3 are all lucky numbers, return the largest of them.
Example 3:
Input: arr = [2,2,2,3,3]
Output: -1
Explanation: There are no lucky numbers in the array.
Constraints:
1 <= arr.length <= 5001 <= arr[i] <= 500
Solutions
Solution 1: Counting
We can use a hash table or an array cnt to count the occurrences of each number in arr. Then, we iterate through cnt to find the largest x such that cnt[x] = x. If there is no such x, return -1.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the arr.
PythonJavaC++GoTypeScriptRustPHP
class Solution:
def findLucky(self, arr: List[int]) -> int:
cnt = Counter(arr)
return max((x for x, v in cnt.items() if x == v), default=-1)(code-box)
class Solution {
public int findLucky(int[] arr) {
int[] cnt = new int[501];
for (int x : arr) {
++cnt[x];
}
for (int x = cnt.length - 1; x > 0; --x) {
if (x == cnt[x]) {
return x;
}
}
return -1;
}
}(code-box)
class Solution {
public:
int findLucky(vector<int>& arr) {
int cnt[501]{};
for (int x : arr) {
++cnt[x];
}
for (int x = 500; x; --x) {
if (x == cnt[x]) {
return x;
}
}
return -1;
}
};(code-box)
func findLucky(arr []int) int {
cnt := [501]int{}
for _, x := range arr {
cnt[x]++
}
for x := len(cnt) - 1; x > 0; x-- {
if x == cnt[x] {
return x
}
}
return -1
}(code-box)
function findLucky(arr: number[]): number {
const cnt: number[] = Array(501).fill(0);
for (const x of arr) {
++cnt[x];
}
for (let x = cnt.length - 1; x; --x) {
if (x === cnt[x]) {
return x;
}
}
return -1;
}(code-box)
use std::collections::HashMap;
impl Solution {
pub fn find_lucky(arr: Vec<i32>) -> i32 {
let mut cnt = HashMap::new();
arr.iter().for_each(|&x| *cnt.entry(x).or_insert(0) += 1);
cnt.iter()
.filter(|(&x, &v)| x == v)
.map(|(&x, _)| x)
.max()
.unwrap_or(-1)
}
}(code-box)
class Solution {
/**
* @param Integer[] $arr
* @return Integer
*/
function findLucky($arr) {
$cnt = array_fill(0, 501, 0);
foreach ($arr as $x) {
$cnt[$x]++;
}
for ($x = 500; $x > 0; $x--) {
if ($cnt[$x] === $x) {
return $x;
}
}
return -1;
}
}(code-box)
