問題解決パターン

最新のソフトウェア エンジニアリングにおける問題解決に関するブログ シリーズへようこそ!

パート 1 では、要素の頻度を効率的にカウントすることでアルゴリズムを最適化するための強力な手法である 周波数カウンター パターン について説明しました。見逃した場合、または簡単に復習したい場合は、続行する前に気軽にチェックしてください。

このパートでは、もう 1 つの重要なパターンであるマルチポインター パターンについて詳しく説明します。このパターンは、複数の要素を同時に比較、検索、または走査する必要があるシナリオを扱う場合に非常に貴重です。これがどのように機能するのか、またコードの効率を向上させるためにどこに適用できるのかを見てみましょう。

02. マルチポインターパターン

マルチポインター パターン は、配列やリンク リストなどのデータ構造を横断するために複数のポインター (または反復子) を使用するアルゴリズム設計で使用される手法です。このパターンでは、単一のポインターまたはループに依存するのではなく、異なる速度または異なる開始点からデータ内を移動する 2 つ以上のポインターを使用します。

問題例

整数のソート配列を受け入れるsumZeroという関数を作成します。関数は、合計がゼロである最初のペアを見つける必要があります。そのようなペアが存在する場合は、両方の値を含む配列を返します。それ以外の場合は、未定義を返します。

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

基本的な解決策

function sumZero(arr){
    for (let i = 0; i < arr.length; i++) {
        for (let j = i+1; j < arr.length; j++) {
            if (arr[i] + arr[j] === 0) {
                console.log(arr[i] + arr[j])
                return [arr[i], arr[j]]
            }
        }
    }
}

時間計算量 - O(N^2)

マルチポインター パターンを使用した解決策

ステップ 1: 問題を理解する
**sorted 配列内で合計が 0 になる 2 つの数値を見つける必要があります。配列はソートされているため、この順序を利用して、より効率的に解を見つけることができます。

ステップ 2: 2 つのポインターを初期化する
2 つのポインターを設定します。1 つは配列の先頭から開始するポインター (left)、もう 1 つは配列の末尾から開始する (right)。

例:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5

ステップ 3: ポインターの値の合計を計算する<🎜​​> 左右のポインターの値を加算して合計を取得します

Sum = -4 + 5 = 1

ステップ 4: 合計をゼロと比較します

• 合計がゼロより大きい場合: 右ポインタを 1 ステップ左に移動して、合計を減らします。

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

• 合計がゼロより小さい場合: 左ポインタを右に 1 ステップ移動して、合計を増やします。

New Sum = -4 + 2 = -2
Sum is -2 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -3
Right Pointer (R): 2

ステップ 5: プロセスを繰り返します ポインタが一致するかペアが見つかるまで、ポインタを移動して合計を計算し続けます。

New Sum = -3 + 2 = -1
Sum is -1 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -2
Right Pointer (R): 2

合計はゼロなので、関数は [-2, 2] を返します。

そのようなペアが見つからずにループが完了した場合は、

未定義を返します。

最終コード

function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left < right) {                // Continue until the pointers meet
    const sum = arr[left] + arr[right]; // Calculate the sum of the values at the pointers

    if (sum === 0) {                    // If the sum is zero, return the pair
      return [arr[left], arr[right]];
    } else if (sum > 0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left++;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}

注:

時間計算量: O(n) – この関数は効率的であり、配列のサイズに応じて線形にスケールします。
空間複雑度: O(1) – この関数は最小限の追加メモリを使用します。

結論

マルチポインター パターンは、ソートされたデータ構造内の要素の検索、比較、操作を伴う問題を解決するための強力な手法です。互いに向かって移動する複数のポインターを使用することで、アルゴリズムの効率を大幅に向上させ、多くの場合、時間の複雑さを O(n²) から O(n) に減らすことができます。このパターンは汎用性が高く、幅広い問題に適用できるため、コードのパフォーマンスを最適化するために不可欠な戦略となります。

次の投稿をお待ちくださいでは、動的データ セグメントに関係する問題に取り組むためのもう 1 つの重要なツールである スライディング ウィンドウ パターン について詳しく説明します。これは、さらに複雑な課題を簡単に解決できる非常に便利なパターンです!

以上が問題解決パターンの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。