【leetcode】1287. Element Appearing More Than 25% In Sorted Ar

时间:2022-01-29 18:25:47

题目如下:

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

Constraints:

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^5

解题思路:最直接的方法是统计每个元素出现的次数。

代码如下:

class Solution(object):
    def findSpecialInteger(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        dic = {}
        res = 0
        for i in arr:
            dic[i] = dic.setdefault(i,0)   1
            if dic[i] > len(arr)/4:
                res = i
                break
        return res