単純なアルゴリズム問題からO(1)が何を意味するかを説明する

[[396914]]

今日、クラスメートがファングループでアルゴリズムに関する質問をしました。

対話のトピックは次のとおりです。

質問では、各要素が 1 回だけ表示されるように、順序付けられた配列 nums から重複する要素を削除する必要があります。削除後の配列の長さを返します。追加の配列スペースは使用されず、空間計算量は O(1) です。

この学生が間違いを犯した理由は、O(1)空間計算量が何を意味するのか理解していなかったからです。実際には 3 行目で新しいリストを生成します。このリストの長さは、元のリストの長さに依存します。元のリスト内の重複しない要素が多いほど、新しいリストは長くなるため、その空間計算量は O(n) になります。さらに、この質問では、新しいリストを生成するのではなく、元のリストを「その場で」変更する必要があります。

まず、O(1)空間計算量とは何かについて説明しましょう。これは、1 つの変数のみを適用できるという意味ではなく、適用する追加変数の数は一定であり、入力リスト内の要素の数に応じて変化しないという意味です。したがって、10,000 個の変数を適用する場合でも、元の入力リストに 1 つの要素がある場合でも 1 億個の要素がある場合でも、常にこれらの 10,000 個の変数のみが使用されるため、空間計算量は O(1) であるとも言えます。

ここで、インプレース変更と呼ばれるものについて説明しましょう。つまり、新しいリストを追加で使用せずに、入力リストを直接変更します。 Python では、リストに要素を追加するには xxx.append(yy) を使用し、インデックスに従ってリストから要素を削除するには xxx.pop(index) を使用することがわかっています。どちらもインプレース変更です。

この質問に戻りますが、これは LeetCode の簡単な質問です。より良いインターネット企業に応募したい場合は、この種の質問に簡単に答えられるはずです。

この問題の鍵となるのは、元のリストが順序付きリストであるため、繰り返される数字が連結されている必要があるということです。したがって、現在の要素が前の要素と同じかどうかを 1 つずつ確認するだけで済みます。同じ場合は、現在の要素を削除します。異なる場合は、次の要素を確認します。

それでは、コードを書いてみましょう:

クラスソリューション:
    重複データを削除します。
        数値でない場合:
 0を返す
最後= なし
インデックス= 0
        長さ = len(数値)
        インデックス< 長さの場合:
            ele = nums[インデックス]
            インデックス== 0 の場合:
最後= 要素
インデックス= 1
            elif ele == last :
                長さ -= 1
                nums.pop(インデックス)
それ以外：
最後= 要素
インデックス+= 1
戻り長さ

実行効果は以下の図に示されています。

この問題の時間計算量は O(n) であることに注意してください。これは、インデックスに従ってリストから要素が削除されると、後続の要素が 1 つずつ前方に移動するためです。一般的に言えば、時間の計算量と空間の計算量を同時に達成することはできません。空間を時間と交換したり、時間を空間と交換したりすることはできますが、空間や時間を占有せずに両方を同時に行うことは困難です。

この記事はWeChatの公開アカウント「WeiwenCode」から転載したもので、以下のQRコードからフォローできます。この記事を転載する場合は、WeiwenCode の公開アカウントにご連絡ください。