Java で二項対立を実装する方法

#順序付けされた配列で、特定の数値が存在するかどうかを確認します

##アイデア:

• 順序付けされた配列であるため、最初に中点の位置を取得でき、中点によって配列を左半分と右半分に分割できます。

• 中点位置の値が目標値と等しい場合は、中点位置を直接返します。

• 中点位置の値が目標値より小さい場合は、配列の中点の左側に移動して同様に検索します。

• 中点位置の値が目標値より大きい場合は、配列の中点の右側を取って同様に検索します。

#最後に見つからない場合は、-1 を返します。
コード

class Solution {
    public int search(int[] arr, int t) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (arr[m] == t) {
                return m;
            } else if (arr[m] > t) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }
}

時間計算量

O(logN)

。 順序付けされた配列で、特定の数値以上の左端の位置を検索します。

例 1:

入力: nums = [1,3,5,6], target = 5

出力: 2

説明: 配列

num## に要素 5 を挿入したい場合#、要素 3 と要素 5 の間、つまり位置 2 に挿入する必要があります。

例 2:

入力: nums = [1,3,5,6]、ターゲット = 2

出力: 1

説明:配列

num

に要素 2 を挿入するには、要素 1 と要素 3 の間の位置、つまり位置 1 に要素 2 を挿入する必要があります。

例 3:

入力: nums = [1,3,5,6]、ターゲット = 7

出力: 4

説明:要素 7 を配列

num

に挿入するには、要素 7 を配列の最後、つまり位置 4 に挿入する必要があります。

上記の例からわかるように、この質問は本質的に「順序付き配列で、特定の数値以上の左端の位置を見つけてください。それが存在しない場合は、戻り値を返します」というものです。配列の長さ (最後に挿入を表す)

上記の例に基づいて簡単な変更を加えるだけで済みます。上記の例で、条件を満たす位置が見つかったら、直接 return

if (arr[m] == t) {
    return m;
}

この質問では、 が等しい場合に左端の位置を見つける必要があるため、直接返さずに最初に位置を記録するだけで済みます。さらに左側を探索していきます。さらに左側に条件を満たす位置はありますか？

同時に、arr[m] > t に遭遇したときは、この時点での

m

の位置も記録する必要があります。も条件を満たす場所である可能性があります。 コード: <pre class='brush:php;toolbar:false;'>class Solution { public static int searchInsert(int[] arr, int t) { int ans = arr.length; int l = 0; int r = arr.length - 1; while (l &lt;= r) { int m = l + ((r - l)&gt;&gt;1); if (arr[m] &gt;= t) { ans = m; r = m - 1; } else { l = m + 1; } } return ans; } }</pre>アルゴリズム全体の時間計算量は

O(logN)

です。

ソートされた配列内の要素の最初と最後の位置を見つける

アイデア

この問題も、2 進除算を使用して解決されます。 2 進除算で要素が見つかった場合は、急いで戻るのではなく、左 (右) に検索を続けて、さらに左 (右) に一致する値が見つかるかどうかを確認します。

コードは次のとおりです:

class Solution {
    public static int[] searchRange(int[] arr, int t) {
        if (arr == null || arr.length < 1) {
            return new int[]{-1, -1};
        }
        return new int[]{left(arr,t),right(arr,t)};   
    }
    public static int left(int[] arr, int t) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        int ans = -1;
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (arr[m] == t) {
               ans = m;
               r = m - 1;
            } else if (arr[m] < t) {
                l = m +1;
            } else {
                // arr[m] > t
                r = m - 1;
            }
        }
        return ans;
    }
    public static int right(int[] arr, int t) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        int ans = -1;
        int l = 0;
        int r = arr.length - 1;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (arr[m] == t) {
               ans = m;
               l = m + 1;
            } else if (arr[m] < t) {
                l = m +1;
            } else {
                // arr[m] > t
                r = m - 1;
            }
        }
        return ans;
    }
}

時間計算量

O(logN)

。

極大問題

アイデア

配列の長さが

N

であると仮定し、最初に # を決定します。 ##0

位置の番号と

N-1 位置の番号はピーク位置ですか? 0 位置は 1

位置と比較するだけで済みます。

0 位置が大きい場合、0 位置 ピーク位置であり、直接戻すことができます。 N-1 位置と N-2

位置を比較するだけで済みます。

N-1 位置の方が大きい場合は、 位置 N-1 はピーク位置であり、直接返すことができます。 0 位置と N-1

が両方とも最後の比較ラウンドの最小値である場合、配列は次のようになります。

上の図からわかるように、

[0..1]

間隔は増加傾向、[N-2.. .N-1]

レンジ内では下降トレンドです。

この場合、ピーク位置は [1...N-2] の間にある必要があります。

このとき、

二分でピーク位置を求めることができます。まず中点位置に移動し、中点位置の値が mid

であると仮定します。 Duda:

arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]

の場合、mid 位置がピーク位置となり、直接戻ります。

それ以外の場合は、次の 2 つの状況が考えられます。

ケース 1: 中間位置の値が中間 - 1 位置の値より小さい

傾向は次のとおりです。 :

は

[1...(mid-1)]

間隔内の 2 つのポイントに分割され続けます。

ケース 2: 中間位置の値が中間 1 位置の値より小さい

傾向は次のとおりです:

则在[(mid+1)...(N-2)]区间内继续上述二分。

完整代码

public class LeetCode_0162_FindPeakElement {
    public static int findPeakElement(int[] nums) {
        if (nums.length == 1) {
            return 0;
        }
        int l = 0;
        int r = nums.length - 1;
        if (nums[l] > nums[l + 1]) {
            return l;
        }
        if (nums[r] > nums[r - 1]) {
            return r;
        }
        l = l + 1;
        r = r - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
                return mid;
            }
            if (nums[mid] < nums[mid + 1]) {
                l = mid + 1;
            } else if (nums[mid] < nums[mid - 1]) {
                r = mid - 1;
            }
        }
        return -1;
    }
}

时间复杂度O(logN)。

以上がJava で二項対立を実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。