Majority Element
長さが n の整数配列 nums が与えられます。配列内に n / 2 回を超えて出現する値があり、その値を多数派要素と呼びます。それを返してください。配列の半分を超えて占める値は必ず一意であるため、答えはちょうど1つです。
関数
- numsinteger-array
- 整数の配列で、ある値が配列の半分を超えて占めているもの
- 戻り値integer
- n / 2 回を超えて出現する値
制約
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109- 1つの値が
nums.length / 2回より多く出現します。
例
- 入力
- nums = [3, 9, 3, 3, 4]
- 出力
- 3
- 説明
- 5つの要素の中に3が3回現れます。3は5 / 2 = 2.5より大きく、9と4はそれぞれ1回現れます。
- 入力
- nums = [8, 8, 1, 1, 8, 1, 8]
- 出力
- 8
- 説明
- 8は4回、1は3回出現します。7個の要素は3.5個より多くのコピーを必要とするため、配列の大部分で1が8に迫っているにもかかわらず、8が多数派です。
提出時に隠しテスト+15件
発展問題
O(n)時間、O(1)の追加メモリで、配列をソートせずに多数派要素を見つけられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
すべての値を数える方法は機能しますが、追加のメモリが必要です。多数派の値は何が特別なのでしょうか？その値の出現回数と、ほかのすべての値を合わせた出現回数を比較します。
多数派のコピーをそれぞれ異なる値と組み合わせ、両方に取り消し線を引きます。多数派はそれ以外のすべてを上回るため、このように組み合わせても、そのコピーの一部は必ず残ります。
候補を1つとカウンターを保持します。要素が候補と一致したら1を加算し、一致しなければ1を減算します。カウンターが0になったら、次の要素を候補にします。最後に残った候補が答えです。
解説
各値が何回現れるかを数えれば答えが分かりますが、その数を数えるにはハッシュマップが必要です。ハッシュマップを使わずに済ませるには、多数派の値が特別な理由に注目します。それは、ほかのすべての値を合わせた数よりも多く現れます。その値の各出現を別の値の出現と組み合わせて両方を消していくと、必ずいくつかが残ります。Boyer-Moore投票法では、候補を1つ、カウンターを1つ使い、1回の走査でこの組み合わせを行います。
ハッシュマップで数える
考え方
配列を順に走査し、各値をキー、その値を見た回数を値とするハッシュマップを保持します。ある値のカウントに1を加えたら、そのカウントが配列の長さの半分を超えたかどうかを確認します。この条件を最初に満たした値が過半数を占める値なので、すぐに返せます。
[3, 9, 3, 3, 4]の場合、3のカウントはインデックス0で1、インデックス2で2、インデックス3で3になります。5個中3個は2.5を超えるので、最後の要素を読むことなく3を返します。
ハッシュマップの検索と更新は平均O(1)で行えるため、時間計算量はO(n)です。マップには最大で約n / 2個の異なる値を保持できるため、追加メモリの計算量はO(n)です。次の方法ではマップを使いません。
アルゴリズム
- 値から出現回数への空のマップを作成します。
- 各要素
xについて、xの出現回数に1を加えます。 - その出現回数に2を掛けた値が配列の長さより大きい場合、
xを返します。
def majorityElement(nums):
counts = {}
for x in nums:
counts[x] = counts.get(x, 0) + 1
if counts[x] * 2 > len(nums):
return xBoyer-Moore投票法
考え方
配列を選挙として考えます。candidate を1つ選び、まだ取り消されていないその票の count を数えます。候補と等しい要素は1票を加えます。異なる要素は1票を取り消し、その2つは一緒に選挙から脱落します。カウントが0になると、次の要素が新しい候補になります。
最後に残った値が過半数である理由は、取り消しのたびに異なる値が2つ取り除かれるため、過半数の値は最大でも1つしか取り除かれないからです。過半数の値が m 回現れるとします。その他の要素は n - m 個しかなく、m より少ないため、過半数の値をすべて取り消すことはできません。最後に残っている票はすべて最終候補のものです。その中には過半数の値も含まれているため、候補が過半数の値です。
[8, 8, 1, 1, 8, 1, 8] では、カウントは 1、2、1、0 と変化します。2つの 1 が2つの 8 を取り消しました。次の 8 でカウント1からやり直し、次の 1 がそれを取り消し、最後の 8 が再び候補になります。8 を返します。変数2つで1回走査すれば、時間計算量は O(n)、メモリ計算量は O(1) です。
アルゴリズム
candidateを最初の要素に、countを0に設定します。- 各要素
xについて、countが0なら、xを候補にします。 xが候補と等しければ、countに1を加えます。そうでなければ、1を引きます。- 最後の要素の後に、
candidateを返します。
def majorityElement(nums):
candidate = nums[0]
count = 0
for x in nums:
if count == 0:
candidate = x # the old candidate's votes are used up
if x == candidate:
count += 1
else:
count -= 1 # x and one copy of the candidate cancel out
return candidate
落とし穴と境界ケース
誤答の多くは、ちょうど半分の境界や、カウンターを深読みすることが原因です。
- 「半分より多い」は厳密な条件です。
count >= n / 2では、4個中2個でも受け入れてしまい、過半数とは言えません。count * 2 > nと比較すれば、丸めによる影響を避けられます。 - Boyer-Mooreにおける最後の
countは、過半数の要素が何回出現したかを示すものではありません。[8, 8, 1, 1, 8, 1, 8]では最終的に1になりますが、8は4回出現しています。 candidate = nums[0]とcount = 1で始める方法が機能するのは、その後ループをインデックス1から開始する場合に限られます。インデックス0から開始すると、最初の要素が2回投票することになります。[1, 2, 2]ではカウントが最終的に0になり、1を返してしまいます。- Boyer-Mooreは、過半数が存在するという保証を前提としています。過半数が存在しない
[1, 2, 3]でも、3を返します。入力に過半数が存在しない可能性がある場合は、候補を信頼する前に2回目の走査でその出現回数を数えてください。
よくある質問4
ボイヤー・ムーアの多数決アルゴリズムとは何ですか？
O(1)のメモリで、リストを1回走査して過半数を占める値を見つけます。候補とカウンターを保持し、一致する要素があれば1を加算し、異なる要素があれば1を減算します。カウンターが0になったら、次の要素が候補になります。過半数の値は、ほかのすべての値を合わせた数より多いため、最後に残った候補がその値です。
Majority Element の時間計算量と空間計算量はどのくらいですか？
Boyer-Moore投票法はO(n)時間、O(1)の追加領域で実行できます。ハッシュマップを使ったカウントもO(n)時間ですが、カウント用にO(n)の領域が必要です。最初にソートすると、O(n log n)時間かかります。
多数要素はソートで解けますか？
はい。ソート後、過半数の要素のすべてのコピーは、配列の半分より長い1つのブロックにまとまり、そのようなブロックは中央の位置を必ず含みます。したがって、インデックス n / 2（小数点以下切り捨て）の要素が答えです。記述は簡潔ですが、時間計算量は O(n log n) です。
配列に過半数を占める要素がない場合はどうでしょうか？
Boyer-Moore は、配列の半分を超える要素が存在しない場合でも、必ず候補を返します。候補の出現回数を数える2回目の走査を追加し、その回数が n / 2 を超える場合にのみ、その候補を受け入れます。全体の計算量は引き続き時間 O(n)、空間 O(1) です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def majorityElement(nums):
# ここにコードを書いてくださいケース1
ケース2
入力
nums = [3, 9, 3, 3, 4]
期待値
3