だから私は小さなリストでうまく機能する関数を持っています。その機能は、シーケンスから1つの要素を削除すると、シーケンスが厳密に増加するシーケンスになるかどうかを確認することです。
def almostIncreasingSequence(sequence):
length = len(sequence)
for i in range(1, length):
newSequence = sequence[:i-1] + sequence[i:]
if checkIfSorted(newSequence, length):
return True
return checkIfSorted(sequence[:length-1], length)
def checkIfSorted(sequence, length):
for i in range(1, length - 1):
if sequence[i-1] >= sequence[i]:
return False
return True
しかし、最大100,000要素の長さのリストで機能するために必要です。これをより速く機能させるために、どのような最適化を行うことができますか？現在、100,000のリストでは非常に遅く、1秒間に数千の要素を処理します。
私はこのサイトにあなたとほぼ同じ質問に答える別の答えを書きましたが、私はシーケンスから最大で1つの要素を削除すると厳密に増加するかどうかを確認するためのものでした。それがあなたの言いたいことかもしれません-実際的な違いはないようです。ここにコピーした私の2番目の解決策が必要なようです。
def first_bad_pair(sequence, k):
"""Return the first index of a pair of elements in sequence[]
for indices k-1, k+1, k+2, k+3, ... where the earlier element is
not less than the later element. If no such pair exists, return -1."""
if 0 < k < len(sequence) - 1:
if sequence[k-1] >= sequence[k+1]:
return k-1
for i in range(k+1, len(sequence)-1):
if sequence[i] >= sequence[i+1]:
return i
return -1
def almostIncreasingSequence(sequence):
"""Return whether it is possible to obtain a strictly increasing
sequence by removing no more than one element from the array."""
j = first_bad_pair(sequence, -1)
if j == -1:
return True # List is increasing
if first_bad_pair(sequence, j) == -1:
return True # Deleting earlier element makes increasing
if first_bad_pair(sequence, j+1) == -1:
return True # Deleting later element makes increasing
return False # Deleting either does not make increasing
私の最初の解決策のように、スライスを結合することによって新しいシーケンスを作成するため、コードは遅くなります。これにより、シーケンスのほぼ全体がコピーされ、それを何度も実行するとコードの速度が低下します。上記のコードは、シーケンスをチェックして厳密に増加しているかどうかを確認するルーチンを複雑にすることで、これを回避しています。詳細については、他のリンクされた回答を確認してください。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加