90. Over a Third
A survey collects one answer code per respondent in the array nums. A code is called a strong signal if more than one third of all respondents chose it, in other words if it appears strictly more than nums.length / 3 times (real division, so with 7 answers a code must appear at least 3 times).
Return every strong signal as an array sorted in ascending order. Each qualifying code appears exactly once in the result, and if no code qualifies you must return an empty array. Note that at most two codes can ever qualify.
Example 1
- Input:
- nums = [4,4,7,2,4,7,7]
- Output:
- [4,7]
- Explanation:
There are 7 answers, so a code needs at least 3 occurrences; both 4 and 7 appear 3 times, giving [4, 7].
Example 2
- Input:
- nums = [5,1,5,5,3,5]
- Output:
- [5]
- Explanation:
Only 5 appears more than 6/3 = 2 times (four times), so the answer is [5].
Constraints
1 ≤ nums.length ≤ 5 * 105
-109 ≤ 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.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)