Majority Element
長さが n の整数配列 nums が与えられます。その中の1つの値は n / 2 回より多く出現し、その値を多数要素と呼びます。それを返してください。配列の半分を超える要素を占める値は必ず一意なので、答えはちょうど1つです。
関数
- numsinteger-array
- 整数の配列で、その半分を超える数の要素が同じ値であるもの
- 戻り値integer
- n / 2 回を超えて出現する値
制約
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109nums.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個より多くのコピーを必要とするため、8が過半数を占めますが、配列の大部分では1も8に並んでいます。
発展問題
すべての値のうち、n / 3 回より多く現れるものを、O(n) 時間、O(1) の追加メモリで見つけられますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
すべての値を数える方法でも機能しますが、余分なメモリが必要です。多数派の値は何が特別なのでしょうか？その値の出現回数と、他のすべての値を合わせた出現回数を比べてみましょう。
多数派の各コピーをそれぞれ異なる値と組み合わせ、両方に取り消し線を引きます。多数派の数は他のすべての値を上回るため、このように組み合わせても多数派のコピーの一部は残ります。
候補を1つとカウンターを保持します。要素が候補と一致したら1を加算し、一致しなければ1を減算します。カウンターが0になったら、次の要素が候補になります。最後に残った候補が答えです。
解説
多数要素の数は、他のすべての値を合わせた数を上回ります。異なる値のペアを取り消していくと、多数要素のコピーが必ずいくつか残ります。Boyer-Moore投票法では、候補値1つとカウンター1つを使って1回の走査でペアを作るため、出現回数を数えるハッシュマップは必要ありません。
ハッシュマップを使って数える
考え方
ハッシュマップで各値の出現回数を数え、出現回数が長さの半分を超える最初の値を返します。[3, 9, 3, 3, 4]の場合、3の出現回数はインデックス3で3回になり、2.5を超えるため、4を読み取る前に返します。
各検索は平均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投票法
考え方
まだ相殺されていない票の数を表すcountと、candidateを保持します。候補と等しい要素は票を1つ加えます。異なる要素は票を1つ相殺し、その2つはどちらも選考から外れます。票数が0になったら、次の要素が候補になります。
相殺のたびに異なる値が2つ取り除かれるため、多数派の値が取り除かれるのは最大でも1つです。多数派がm回現れるとき、残りのn - m個の要素数はmより少ないので、多数派の値をすべて相殺することはできません。最後まで残った票はすべて最終候補のものであり、その中には多数派の値が少なくとも1つ含まれます。
[8, 8, 1, 1, 8, 1, 8]では、1が2つの8を相殺するにつれて、票数は1、2、1、0と変化します。次の8で票数は1から再開し、その次の1がそれを相殺し、最後の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と比較すれば、丸めが影響することはありません。 - 最後の
countを過半数の頻度として読み取ってしまうこと。[8, 8, 1, 1, 8, 1, 8]の場合、8は4回出現しますが、最後の値は1になります。 candidate = nums[0]とcount = 1で開始し、その後インデックス0からループすること。最初の要素が2回投票します。[1, 2, 2]では、countが0になり、1を返します。
よくある質問3
多数決要素の時間計算量と空間計算量は何ですか？
Boyer-Moore 投票算法的运行时间为 O(n)，额外空间复杂度为 O(1)。使用哈希映射计数的时间复杂度也为 O(n)，但需要 O(n) 的空间来存储计数。先排序则需要 O(n log n) 的时间。
多数要素はソートで解けますか？
はい。ソート後は、過半数の要素がすべて、配列の半分より長い1つの区間に集まっており、そのような区間は中央の位置を必ず含みます。したがって、インデックス n / 2（小数点以下切り捨て）の要素が答えとなり、時間計算量は O(n log n) です。
配列に過半数を占める要素がない場合はどうでしょうか？
Boyer-Mooreは必ず何らかの候補を返します。[1, 2, 3]の場合は3を返します。2回目の走査を追加して候補の出現回数を数え、その回数がn / 2より多い場合にのみ採用します。全体の計算量は引き続き時間O(n)、空間O(1)です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def majorityElement(nums):
# ここにコードを書いてくださいテスト #1
テスト #2
引数
nums = [3, 9, 3, 3, 4]
期待される出力
3