Java2ポインタ技術

投稿日: 2019-10-19 2022-10-26
タグ: Java

1. 概要

このチュートリアルでは、配列とリストに関連する問題を解決するための2ポインターアプローチについて説明します。 この手法は、アルゴリズムのパフォーマンスを向上させるための簡単で効率的な方法です。

2. テクニックの説明

配列またはリストに関連する多くの問題では、配列の各要素を他の要素と比較して分析する必要があります。

このような問題を解決するために、通常、最初のインデックスから開始し、実装に応じて配列を1回以上ループします。問題の要件に応じて、一時配列を作成する必要がある場合もあります。

上記のアプローチでは正しい結果が得られる可能性がありますが、スペースと時間の効率が最も高いソリューションにはならない可能性があります。

その結果、2ポインターアプローチを使用して問題を効率的に解決できるかどうかを検討することをお勧めします。

2ポインターのアプローチでは、ポインターは配列のインデックスを参照します。ポインタを使用することで、ループごとに1つではなく2つの要素を処理できます。

2ポインターアプローチの一般的なパターンには、次のものがあります。

それぞれ最初と最後から始まり、両方が出会うまでの2つのポインタ
一方のポインターは遅いペースで移動し、もう一方のポインターは速いペースで移動します

上記のパターンは両方とも、問題の時間とスペースの複雑さを減らすのに役立ちます。これは、より少ない反復で、あまり多くの追加スペースを使用せずに、期待される結果が得られるためです。

それでは、このテクニックをもう少しよく理解するのに役立ついくつかの例を見てみましょう。

3. 合計は配列に存在します

問題：整数のソートされた配列が与えられた場合、それらの合計が特定の値に等しくなるように、その中に2つの数値があるかどうかを確認する必要があります。

たとえば、入力配列が [1、1、2、3、4、6、8、9] で、ターゲット値が 11 の場合、メソッドは[ X136X]true。ただし、ターゲット値が 20 の場合、falseを返す必要があります。

まず、単純な解決策を見てみましょう。

public boolean twoSumSlow(int[] input, int targetValue) {

    for (int i = 0; i < input.length; i++) {
        for (int j = 1; j < input.length; j++) {
            if (input[i] + input[j] == targetValue) {
                return true;
            }
        }
    }
    return false;
}

上記のソリューションでは、入力配列を2回ループして、可能なすべての組み合わせを取得しました。組み合わせの合計を目標値と照合し、一致する場合はtrueを返しました。 このソリューションの時間計算量はO（n ^ 2）です。 。

ここで、2ポインター手法をどのように適用できるかを見てみましょう。

public boolean twoSum(int[] input, int targetValue) {

    int pointerOne = 0;
    int pointerTwo = input.length - 1;

    while (pointerOne < pointerTwo) {
        int sum = input[pointerOne] + input[pointerTwo];

        if (sum == targetValue) {
            return true;
        } else if (sum < targetValue) {
            pointerOne++;
        } else {
            pointerTwo--;
        }
    }

    return false;
}

配列はすでにソートされているため、2つのポインターを使用できます。 1つのポインターは配列の先頭から始まり、もう1つのポインターは配列の終わりから始まります。次に、これらのポインターに値を追加します。値の合計が目標値よりも小さい場合は、左のポインターをインクリメントし、合計が目標値よりも大きい場合は、右のポインターをデクリメントします。

ターゲット値と一致する合計が得られるか、配列の中央に到達し、組み合わせが見つからなくなるまで、これらのポインターを移動し続けます。 このソリューションの時間計算量はO（n）であり、空間計算量はO（1） $であり、$ 最初の実装よりも大幅に改善されています。

4. アレイの回転kステップ

問題：配列が与えられた場合、 k ステップで配列を右に回転します。ここで、kは負ではありません。たとえば、入力配列が [1、2、3、4、5、6、7] で、kが4の場合、出力は次のようになります。 [4、5、6、7、1、2、3]になります。

これを解決するには、2つのループを再度使用して、時間計算量 O（n ^ 2）を作成するか、追加の一時配列を使用しますが、これにより、時間計算量 O（n）が作成されます。 。

代わりに、2ポインター手法を使用してこれを解決しましょう。

public void rotate(int[] input, int step) {
    step %= input.length;
    reverse(input, 0, input.length - 1);
    reverse(input, 0, step - 1);
    reverse(input, step, input.length - 1);
}

private void reverse(int[] input, int start, int end) {
    while (start < end) {
        int temp = input[start];
        input[start] = input[end];
        input[end] = temp;
        start++;
        end--;
    }
}

上記の方法では、必要な結果を得るために、入力配列のセクションをインプレースで複数回反転します。セクションを逆にするために、配列セクションの両端で要素の交換が行われる2ポインターアプローチを使用しました。

具体的には、最初に配列のすべての要素を逆にします。次に、最初の k 要素を逆にしてから、残りの要素を逆にします。 このソリューションの時間計算量はO（n）であり、 $空間計算量はO（1）です。$

5. LinkedListの中央要素

問題：単一の LinkedList が与えられた場合、その中央の要素を見つけます。たとえば、入力LinkedListが1->2-> 3-> 4-> 5、の場合、出力は3になります。

LinkedList のような配列に似た他のデータ構造でも、2ポインター手法を使用できます。

public <T> T findMiddle(MyNode<T> head) {
    MyNode<T> slowPointer = head;
    MyNode<T> fastPointer = head;

    while (fastPointer.next != null && fastPointer.next.next != null) {
        fastPointer = fastPointer.next.next;
        slowPointer = slowPointer.next;
    }
    return slowPointer.data;
}

このアプローチでは、2つのポインターを使用してリンクリストをトラバースします。一方のポインタは1つインクリメントされ、もう一方は2つインクリメントされます。高速ポインタが最後に到達すると、低速ポインタはリンクリストの中央に配置されます。 このソリューションの時間計算量はO（n）であり、空間計算量はO（1）です。

6. 結論

この記事では、いくつかの例を見て、2ポインター手法をどのように適用できるかについて説明し、それがアルゴリズムの効率をどのように改善するかを調べました。

この記事のコードは、Githubでから入手できます。

getdocs

13036