Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Example 1:
Input: nums = [3,2,3]
Output: [3]
Example 2:
Input: nums = [1]
Output: [1]
Example 3:
Input: nums = [1,2]
Output: [1,2]
Constraints:
-
1 <= nums.length <= 5 * 104 -
-109 <= nums[i] <= 109
Follow up: Could you solve the problem in linear time and in O(1) space?
SOLUTION:
# class Solution:
# def majorityElement(self, nums: List[int]) -> List[int]:
# k = len(nums) // 3
# ctr = {}
# for num in nums:
# ctr[num] = ctr.get(num, 0) + 1
# return [num for num, count in ctr.items() if count > k]
class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
nums.sort()
n = len(nums)
elms = set(nums)
op = []
for x in elms:
ctr = bisect.bisect_right(nums, x) - bisect.bisect_left(nums, x)
if ctr > n // 3:
op.append(x)
return op
Top comments (0)