Pythonでソート済み配列内の数値が過半数要素（マジョリティ要素）かどうかを判定する方法

問題概要

非降順（昇順）にソートされた整数配列 nums と、ある数値 target が与えられます。この target が「過半数要素（マジョリティ要素）」であるかどうかを判定してください。ここで、長さ N の配列における過半数要素とは、配列内に N/2 回より多く出現する要素のことを指します。

例えば、配列が [2,4,5,5,5,5,5,6,6] で target が 5 の場合を考えてみましょう。配列の長さは 9 なので、9/2 = 4.5 より多く出現すれば過半数要素です。実際、5 は 5 回出現しているため条件を満たし、出力は true になります。

解法のアプローチ：二分探索の活用

配列がすでにソートされているため、二分探索を利用することで O(log n) の時間計算量で効率的に解くことができます。線形に要素を数える方法（O(n)）よりも高速です。具体的には、target が出現する範囲の左端と右端を求めるための、次の2つのヘルパー関数を実装します。

lower() 関数：最初の出現位置を見つける

target が最初に出現するインデックス（左端）を二分探索で求めます。引数として配列 arr と target を受け取ります。

• low := 0、high := 配列の長さ
• low < high の間、以下を繰り返します。
  • mid := low + (high - low) / 2
  • arr[mid] == target なら high = mid、そうでなければ low = mid + 1
• arr[high] == target なら high を返し、それ以外の場合は -1 を返します。

upper() 関数：最後の出現位置を見つける

target が最後に出現するインデックス（右端）を二分探索で求めます。

• low = 0、high = 配列の長さ
• low < high の間、以下を繰り返します。
  • mid = low + (high - low) / 2
  • arr[mid] == target なら low = mid、そうでなければ high = mid - 1
• arr[low] == target なら low を返し、それ以外の場合は -1 を返します。

メイン処理の流れ

• u := upper(arr, target)
• l := lower(arr, target)
• u が -1 でない場合、(u - l + 1) > len(nums) / 2 なら true を返し、それ以外は false を返します。

つまり、「右端のインデックス − 左端のインデックス + 1」が target の出現回数となるため、これが配列長の半分を超えているかどうかを確認すればよいわけです。

Pythonでの実装例

以下のコードで実際の動作を確認してみましょう。

class Solution(object):
    def upper(self,n,target):
        low = 0
        high = len(n)-1
        while low<high:
            mid = low + (high - low + 1)//2
            if n[mid] == target:
                low = mid
            else:
                high = mid-1
        return low if n[low] == target else -1
    def lower(self,n,target):
        low = 0
        high = len(n)-1
        while low < high:
            mid = low + (high - low)//2
            if n[mid]== target:
                high = mid
            else :
                low = mid +1
        return high if n[high] == target else -1
    def isMajorityElement(self, nums, target):
        u = self.upper(nums,target)
        l = self.lower(nums,target)
        return u-l+1 >len(nums)/2 if u != -1 else False
ob1 = Solution()
print(ob1.isMajorityElement([2,4,5,5,5,5,5,6,6], 5))

入力

[2,4,5,5,5,5,5,6,6]
5

出力

true

計算量の評価

このアルゴリズムでは、lower() と upper() のそれぞれで二分探索を1回ずつ行うため、時間計算量は O(log n)、追加で必要な空間計算量は O(1) となります。ソート済み配列という前提条件を活かした非常に効率的なアプローチであり、大規模なデータに対しても高速に動作します。