Java配列高周波テストポイント解析例

1. 配列理論の基礎

配列とは、連続したメモリ空間に格納された同じ種類のデータの集合であり、添字の下にある対応するデータは添字インデックスによって取得できます。

例 (文字配列)~

次のようになります:

1. 配列の添字は 0 から始まります

2. メモリ上の配列のアドレスは連続した

であるため、要素を削除する場合は上書きしか使用できません。

たとえば、インデックス 2~ の要素を削除する場合、削除する要素を覆うように、2 以降の要素を順番に前の要素に移動する必要があります。

したがって、要素を削除すると、要素のスペースは解放されませんが、背後のスペースが解放されます。要素を前に移動し、削除する要素を上書きし、配列の長さから 1 を減算すると、一見新しい配列が得られます。

Java における 2 次元配列の格納方法は次のとおりです:

2.共通テストのポイント

1.Binary search

Likou 質問リンク: バイナリ検索

この質問の前提は順序付けされた配列です。要素が繰り返されると、バイナリ検索メソッドによって返される要素の添え字が一意ではなくなる可能性があるためです。これらはすべて二項対立の前提条件を使用しています。

二分探索の考え方は次のとおりです。

配列が順序付けされている (昇順を想定) という前提の下で、配列の中央の値が配列の値よりも大きい場合、見つかった場合、後半部分にある要素は見つからないため、後半部分の値が中央の値より大きいため、最初の比較を通じて範囲を半分に減らすことができます。同様に当てはまります。要素を見つける時間計算量が O(logN) である必要があるとき、まずそれが分割できるかどうかを考えてください。 2つの部分に分かれていますか？

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }
}

2. 要素を削除する

学生の中には、冗長な要素を削除すればよいと言う人もいるかもしれません。ただし、配列の要素はメモリ アドレス内で連続していることを知っておく必要があり、配列内の要素を個別に削除することはできず、上書きすることしかできません。

例: 配列と val 値を指定すると、val 値に等しい配列内の要素を削除する必要があります。これを行うにはどうすればよいですか?

アイデア 1: 残酷な方法

2 つの for ループを使用できます。val 値に等しい要素に移動するとき、次の要素全体を前方に移動して、削除する要素をカバーします。 、しかし、このアプローチは明らかに時間の複雑さが高すぎます。

class Solution {
    public int removeElement(int[] nums, int val) {
        int size = nums.length;
        for (int i = 0; i < size;i++ ) {
            if (nums[i] == val) { // 发现需要移除的元素，就将数组后面集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--;
            }
        }
        return size;
    }
}

アイデア 2: ダブル ポインタ メソッド

高速ポインタと低速ポインタをそれぞれ設定し、低速ポインタを高速に設定すると、2 つは一緒に移動します。低速ポインタは、削除する要素に遭遇すると停止します。削除（上書き）; 高速ポインタが残すべき要素に到達したら、高速ポインタの要素を低速ポインタに割り当て、その後、高速ポインタが終わるまで 2 つのポインタが同時に後方に移動します。ポインタは配列全体を走査します。

これは次のように理解できます: 配列の新しい長さ newLength を 0 から定義し、配列を高速に走査する高速ポインターを定義します。高速が残すべき要素に到達すると、その要素が新しい配列に追加する必要があります (つまり、 newLength 添字に追加されます。これは、返される新しい配列として newLength がみなされる前の配列の部分に相当します。これは、この新しい配列に要素を挿入するのと同じです) ）。

class Solution {
    public int removeElement(int[] nums, int val) {
        int fast = 0;// 定义一个快指针遍历数组
        int newLength = 0;// 定义新的数组长度
        while(fast < nums.length){
            if(nums[fast] != val){
                nums[newLength++] = nums[fast];
            }
            fast++;
        }
        return newLength;
    }
}

推奨される質問

1. 並べ替えられた配列内の重複を削除します

2. ゼロを移動します

3. バックスペースを含む文字を比較します。 ##4. 順序付けされた配列の 2 乗

他の多くの一般的な配列テスト ポイントは、これら 2 つのポイントに基づいており、配列の追加、削除、変更、チェック、検索と検索の習得に他なりません。配列を削除すると、質問に答え始めることができます。

以上がJava配列高周波テストポイント解析例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。