Description
https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/
Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time, return that integer.
Example 1:
Input: arr = [1,2,2,6,6,6,6,7,10] Output: 6
Example 2:
Input: arr = [1,1] Output: 1
Constraints:
1 <= arr.length <= 1040 <= arr[i] <= 105
Explanation
Find the element which occurs more than 25 % of len(arr).
Python Solution
class Solution:
def findSpecialInteger(self, arr: List[int]) -> int:
percent_25_count = len(arr) // 4
counter = {}
for num in arr:
counter[num] = counter.get(num, 0) + 1
for key, value in counter.items():
if value > percent_25_count:
return key- Time Complexity: O(N).
- Space Complexity: O(N).