Leetcode 1287:秩序配列に25%以上出現する要素(超詳細解法!!)

減算されていない秩序化された整数配列を与えます.この配列には、配列要素の総数の25%を超える整数が適切に存在することが知られています.
この整数を見つけて返してください
例:

  ：arr = [1,2,2,6,6,6,6,7,10]
  ：6

ヒント:

1 <= arr.length <= 10^4

0 <= arr[i] <= 10^5

問題を解く構想.
この問題はまず暴力解法、つまりすべての要素を統計してから、最も多くの要素が25%を超えるかどうかを考えるのが難しくない.pythonにCounter().most_common(1)を使用すればよい.

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        return collections.Counter(arr).most_common(1)[0][0]

この問題のより良い解法は,二分法(問題で与えられた条件は秩序整数配列)によりpythonにbisectのパケットを用いることでよい.では、私たちはすべての要素を遍歴する必要がありますか?必要ありません.1/4の位置ごとに要素を抽出し、条件に合致するかどうかを判断するだけでよい(配列が秩序化されているため、すべてそうすることができる).

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        n = len(arr)
        for i in range(0, n, n//4 + 1):
            if bisect.bisect(arr, arr[i]) - bisect.bisect_left(arr, arr[i]) > n//4 : 
                return arr[i]

この問題の他の言語バージョンをGitHub Leetcodeに追加しました
もし問題があれば、皆さんに指摘してほしい!!!