Check if an Array Is Sorted
整数の配列 nums が与えられます。非減少順、つまり各要素がその次の要素以下である場合は true を返し、そうでなければ false を返してください。隣り合う要素が等しくても問題ありません。[2, 2, 3] はソート済みとみなされます。要素が1つの配列はソート済みです。
関数
- numsinteger-array
- チェックする整数の配列
- 戻り値boolean
- すべての要素が次の要素以下である場合は true、それ以外の場合は false
制約
1 ≤ nums.length ≤ 5000-109 ≤ nums[i] ≤ 109
例
- 入力
- nums = [1, 3, 3, 7]
- 出力
- true
- 説明
- 各ステップでは数値が増加するか、同じ値のままです。1から3、3から3、3から7です。3が繰り返されてもよいので、答えは
trueです。
- 入力
- nums = [2, 5, 4, 9]
- 出力
- false
- 説明
- 5から4への移動は下向きです。このような移動が1回あるだけで配列は未整列になります。最後の9が最大値であっても同じなので、答えは
falseです。
提出時に隠しテスト+16件
発展問題
昇順または降順のどちらかに並べ替えられている可能性がある配列を、1回の走査でどのように確認しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
配列がソートされていない場合、どこを見ればそれがわかりますか？離れた位置にある要素を比較する必要がありますか？
各要素を、そのすぐ後ろにある要素と比較すれば十分です。隣り合う要素が等しくても問題ありません。順序が崩れるのは、値が下がる場合だけです。
隣り合うペアを順に調べ、左側の値が右側の値より大きい最初のペアで
falseを返します。そのようなペアがなければ、trueを返します。
解説
配列がソートされているのは、どの要素も直後の要素より大きくない場合です。離れた要素同士を比較する必要はありません。隣り合うすべてのペアが順序どおりなら、配列全体も順序どおりです。これにより、最初に順序が崩れた箇所で終了できる、n-1 個のペアを1回走査するチェックになります。
コピーを並べ替えて比較する
考え方
ソート済みの配列とは、ソートしても変化しない配列です。そこで、nums のコピーを作り、そのコピーをソートして、元の配列と位置ごとに一致するか確認します。すべての位置が一致すれば、nums はすでに整列されています。
[2, 5, 4, 9] の場合、ソートしたコピーは [2, 4, 5, 9] です。位置 1 には、元の配列では 5、コピーでは 4 があるため、答えは false です。[1, 3, 3, 7] の場合、コピーは元の配列と同じなので、答えは true です。
これは正しい方法ですが、問題で求められている以上のことをしています。ソートには O(n log n) のコストがかかり、5000 個の数値では比較が約 6 × 10^4 回必要です。また、コピーには O(n) のメモリが必要です。さらに、最初のペアがすでに順不同でも、配列全体を必ず読み込みます。
アルゴリズム
- 元の値が変更されないように、
numsをコピーします。 - コピーを数値の昇順に並べ替えます。
- コピーと
numsを、位置ごとに比較します。 - すべての位置が一致する場合は
trueを、そうでない場合はfalseを返します。
def isSorted(nums):
# sorted returns a new list, so nums itself is left as it was.
return sorted(nums) == nums隣り合う各ペアを比較する
考え方
配列がソートされているかどうかを知るのに、ソート済みの配列は必要ありません。配列が非減少順であるのは、各要素が直後の要素以下である場合に限ります。≤ は推移するため（a ≤ b と b ≤ c なら a ≤ c）、隣り合う n-1 組を調べれば、すべての位置の組を網羅できます。
i を 1 から n-1 まで動かし、nums[i-1] と nums[i] を比較します。[2, 5, 4, 9] の場合、(2, 5) の組は問題ありませんが、(5, 4) の組で値が下がるため、9 を調べることなく、その時点で false を返します。隣り合う値が等しい場合は条件を満たします。失敗するのは > の場合だけだからです。
各組を一度ずつ比較するため、時間計算量は O(n) で、追加メモリはループのインデックスだけなので O(1) です。値を引き算するのではなく、2つの値を直接比較してください。値が 10^9 までの場合、差が32ビット整数の範囲を超える可能性があります。
アルゴリズム
iを 1 からn-1までループします。nums[i-1] > nums[i]の場合、falseを返します。- ループが終了したら、
trueを返します。要素が1つの場合はループをスキップし、ソート済みです。
def isSorted(nums):
for i in range(1, len(nums)):
# One step down anywhere breaks the order.
if nums[i - 1] > nums[i]:
return False
return True
落とし穴と境界ケース
ループは短いため、バグはその端と比較処理に潜んでいます。
- 等しい隣接要素を失敗として扱う。
nums[i-1] >= nums[i]をテストすると、[1, 3, 3, 7]は拒否されます。順序を崩すのは、厳密な降順のステップ（>）だけです。 - 末尾の先を読み取る。
0からn-1までのループでnums[i]とnums[i+1]を比較する場合、配列の範囲外を読み取らないよう、1つ手前で止める必要があります。i = 1から始めてi-1と比較すれば、この問題を避けられます。 - 比較の代わりに減算する。
nums[i] - nums[i-1] >= 0は同じように見えますが、10^9 - (-10^9) = 2 × 10^9は32ビット整数に収まらず、負の数にラップアラウンドするため、[-1000000000, 1000000000]はソートされていないと判定されます。x - yと書かれた qsort の比較関数でも、同じオーバーフローが問題になります。 - 数値をテキストとしてソートする。JavaScript では、比較関数を指定せずに
sort()を使うと、10は9より前に並ぶため、ソートして比較する方法では誤った答えになります。
よくある質問4
配列がソートされているかどうかは、どうすれば確認できますか？
各要素を次の要素と比較します。右隣の要素より大きい要素があれば、配列はソートされていないので、そこで終了できます。見つからないまま最後まで到達した場合は、ソートされています。これには O(n) の時間と O(1) の追加領域が必要です。
なぜ隣接するものを確認するだけで十分なのでしょうか？
順序関係は推移します。a ≤ b かつ b ≤ c なら、a ≤ c です。したがって、隣接するすべての要素の組が順序どおりなら、位置のすべての組も順序どおりです。逆に、ソートされていない配列には、値が小さくなる隣接要素の組が少なくとも1つあります。
要素がすべて等しい配列はソート済みですか？
非減少順になっています。はい、[4, 4, 4] は、どの要素も次の要素より大きくないため、ソートされています。問題で厳密な昇順を求められている場合は、隣り合う要素が等しい場合も拒否するように判定を変更してください。
コピーを並べ替えて、元のものと比較できますか？
はい、正しい答えが得られますが、コピーに O(n log n) の時間と O(n) の追加メモリが必要です。隣接要素のチェックはより高速で、コピーも不要です。また、残りを読み込まずに、最初に下降する箇所で結果を返せます。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def isSorted(nums):
# ここにコードを書いてくださいケース1
ケース2
入力
nums = [1, 3, 3, 7]
期待値
true