86. Self-Counting Value
A museum turnstile records a positive ticket-class number for every visitor, producing the array nums. A class number v is called self-counting if exactly v visitors in the array hold class v; for example, class 3 would be self-counting if the number 3 appeared exactly three times.
Return the largest self-counting class number found in nums. Class numbers that do not occur in the array at all are never candidates. If no class number is self-counting, return -1.
Example 1
- Input:
- nums = [6,2,6,1,2]
- Output:
- 2
- Explanation:
Value 1 appears once and value 2 appears twice, so both are self-counting; 6 appears twice and is not. The largest is 2.
Example 2
- Input:
- nums = [5,5,5,4,4]
- Output:
- -1
- Explanation:
5 appears 3 times and 4 appears 2 times, so no value equals its frequency and the answer is -1.
Constraints
1 ≤ nums.length ≤ 105
1 ≤ nums[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(n)