Leaders in an Array
整数の配列 nums が与えられます。要素がその右側にあるすべての要素以上であるとき、その要素をリーダーといいます。最後の要素の右側には要素がないため、常にリーダーです。nums の左から右への順序で、すべてのリーダーを返してください。
関数
- numsinteger-array
- 検索する整数の配列
- 戻り値integer-array
- nums のリーダーを左から右へ
制約
1 ≤ nums.length ≤ 25000-109 ≤ nums[i] ≤ 109
例
- 入力
- nums = [12, 5, 9, 3, 6, 2]
- 出力
- [12, 9, 6, 2]
- 説明
- 2が最後なので、先頭になります。6はその後ろにある2より大きく、9は3、6、2より大きく、12はすべてより大きいです。5は9に負け、3は6に負けるので、答えは
[12, 9, 6, 2]です。
- 入力
- nums = [4, 7, 7, 1, 7]
- 出力
- [7, 7, 7]
- 説明
- 同点のカウント：インデックス1と2の7は、右側に同じ7があるだけなので、最後の7とともにすべて先頭に並びます。4と1のそれぞれの後ろには7があります。
- 入力
- nums = [-3]
- 出力
- [-3]
- 説明
- 単一の要素は最後の要素なので、負の値かどうかにかかわらず、リーダーです。
発展問題
値が1つずつ届き、その都度、ここまでのリーダーを報告する必要がある場合、値ごとの償却時間 O(1) でリストをどのように更新しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
nums[i]がリーダーかどうかを判断するには、その右側の部分に関する数値が1つだけ必要です。それは何でしょうか？要素がリーダーとなるのは、その右側にあるすべての要素の最大値以上である場合に限ります。右端から順に進めば、進みながらその最大値を更新できます。
最後の要素を、最初に見つかったリーダーであり、現在の最大値でもあるものとして始めます。左へ進み、現在の最大値以上の各値をリーダーとして、これを新しい最大値にします。リーダーは右から左へ集めるため、返す前に逆順にします。
解説
左から読み進めると、各要素について、その後ろにある部分を新たに走査する必要があります。代わりに右から進めましょう。その後ろの部分について知る必要があるのは最大値だけで、それを1つの変数に保持できます。これにより、O(n²) のチェックを1回の走査で済ませられます。
右側のすべてを確認する
正しいが、最大のテストでは終わらない
考え方
定義を適用します。各インデックス i について、後続の要素を調べ、nums[i] より厳密に大きい最初の要素で停止します。最後まで調べても見つからなければ、nums[i] はリーダーです。インデックスを左から右へ調べるので、リーダーも順番どおりに見つかります。[12, 5, 9, 3, 6, 2] では、5 は 9 で止まり、3 は 6 で止まります。
コストがかかるのは、最後まで続く走査です。等しい値が24,999個並び、その後に1つだけ大きい値が続く場合、各要素は配列のほぼ全体を走査します。比較回数は約25,000 × 25,000 / 2、つまり3 × 10^8回を超えます。
アルゴリズム
- 空の結果リストを作成します。
- 各インデックス
iについて、jをi + 1から末尾まで走査します。 nums[j]のいずれかがnums[i]より大きければ、そこで停止します。nums[i]はリーダーではありません。- そのような
jが存在しない場合は、nums[i]を結果に追加します。 - 結果を返します。
def leaders(nums):
n = len(nums)
result = []
for i in range(n):
is_leader = True
for j in range(i + 1, n):
if nums[j] > nums[i]: # a bigger value on the right rules it out
is_leader = False
break
if is_leader:
result.append(nums[i])
return result右から一度走査しながら最大値を更新
考え方
右側のすべての要素以上の大きさであることは、それらの最大値以上の大きさであることと同じです。右から左へ進みながら、その最大値を常に更新できます。最後の要素が最初のリーダーとなり、最大値になります。その左にある各要素は、最大値以上であればリーダーとなり、その後新しい最大値になります。そうでなければ、右側にそれより大きな値があります。
[12, 5, 9, 3, 6, 2]の場合、2がリーダーとなり、次に6、次に9、そして12がリーダーとなります。一方、3と5は最大値を下回ります。[2, 6, 9, 12]が見つかりました。逆順にすると、それが答えです。
各要素は1回比較されます。時間計算量はO(n)、結果以外の追加領域はO(1)です。R版ではリーダーをlogical(n)ベクトルに記録するため、追加領域はO(n)です。
アルゴリズム
- 結果の最後の要素にし、
bestをその値に設定します。 iを最後から2番目のインデックスから0まで移動させます。nums[i] ≥ bestの場合、結果にnums[i]を追加し、bestをその値に設定します。- 結果を逆順にしてリーダーが左から右に並ぶようにし、それを返します。
def leaders(nums):
n = len(nums)
best = nums[n - 1] # the largest value to the right of the current index
found = [best] # the last element is always a leader
for i in range(n - 2, -1, -1):
if nums[i] >= best:
best = nums[i]
found.append(nums[i])
found.reverse() # collected right to left, returned left to right
return found
落とし穴と境界ケース
- 走査中の最大値と比較するときに、
≥ではなく>を使うこと。[4, 7, 7, 1, 7]では、7はすべてリーダーになりますが、厳密な比較をすると最後の7だけが残ります。 - 最大値を最後の要素ではなく0に設定すること。
[-1, -5]では両方を返す必要がありますが、最大値を0にすると除外されてしまいます。 - リーダーを見つけた順に返すこと。
[12, 9, 6, 2]ではなく[2, 6, 9, 12]になります。 - 最後の要素をすでに結果に追加しているのに、ループを最後のインデックスから開始して、最後の要素を2回追加すること。
- 各要素を隣の要素とのみ比較すること。
[5, 3, 9]では、5は隣の3より大きいですが、9があるため答えは[9]です。
よくある質問3
配列内のリーダーを見つける時間計算量はどれくらいですか？
右から1回走査するため O(n) です。各要素は、更新される最大値と1回比較されます。各要素を右側のすべての要素と比較すると、最悪の場合は O(n²) かかります。たとえば、すべての値が等しい場合です。
最後の要素は常にリーダーですか？
はい。リーダーは右側にあるすべての要素以上の大きさでなければならず、最後の要素には右側に要素がないため、確認するものがなくても条件を満たします。
等しい値もリーダーとして数えますか？
ここでは、はい。リーダーは右側にあるすべての要素以上でなければならないため、[4, 7, 7, 1, 7] では3つの7すべてがリーダーです。厳密に大きいことを求めるバージョンもあります。その場合は > で比較し、同じ値の中では最後の値だけがリーダーになります。
def leaders(nums):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [12, 5, 9, 3, 6, 2]
期待される出力
[12, 9, 6, 2]