Analisis contoh titik ujian frekuensi tinggi tatasusunan Java

1. Asas teori tatasusunan

Tatasusunan ialah koleksi jenis data yang sama yang disimpan dalam ruang memori berterusan Data yang sepadan di bawah subskrip boleh diperoleh melalui pengindeksan subskrip.

Contohnya (susunan aksara)~

Anda boleh lihat:

1 Subskrip tatasusunan bermula dari 0

2. Alamat tatasusunan dalam memori adalah berterusan

Jadi apabila memadamkan elemen, anda hanya boleh menggunakan menulis ganti.

Sebagai contoh, jika anda ingin memadamkan elemen dengan indeks 2~, anda perlu mengalihkan elemen selepas 2 ke yang sebelumnya mengikut urutan, meliputi elemen yang akan dipadamkan.

Jadi pemadaman elemen tidak melepaskan ruang elemen, tetapi ruang di belakang Gerakkan elemen ke hadapan, tulis ganti elemen yang hendak dipadamkan, dan kemudian tolak 1 daripada panjang tatasusunan untuk mendapatkan tatasusunan yang kelihatan baharu.

Di java, kaedah penyimpanan tatasusunan dua dimensi adalah seperti berikut:

2 Titik ujian biasa

1 carian

Pautan kepada soalan: Carian binari

Premis soalan ini ialah tatasusunan tertib, kerana apabila terdapat elemen berulang, subskrip elemen yang dikembalikan oleh kaedah carian binari mungkin tidak unik Ini semua menggunakan Prasyarat untuk dikotomi.

Idea carian binari ialah:

Di bawah premis bahawa tatasusunan disusun (dengan mengandaikan tertib menaik), jika nilai di tengah tatasusunan lebih besar daripada nilai kepada ditemui, maka elemen yang ditemui tidak boleh berada di bahagian separuh kedua, kerana nilai pada separuh kedua lebih besar daripada nilai tengah, jadi melalui perbandingan pertama, julat boleh dikurangkan separuh kemudian, iaitu, kerumitan masa dikurangkan kepada O(logN), dan kecekapan bertambah baik apabila soalan Apabila kerumitan masa mencari elemen diperlukan untuk menjadi O(logN), mula-mula fikirkan sama ada ia boleh dibahagikan kepada dua bahagian?

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. Alih keluar elemen

Sesetengah pelajar mungkin berkata, bukankah anda patut memadamkan elemen yang berlebihan? Tetapi anda mesti tahu bahawa elemen tatasusunan adalah berterusan dalam alamat memori Anda tidak boleh memadamkan elemen dalam tatasusunan secara individu, anda hanya boleh menulis gantinya.

Contohnya: Saya memberikan anda tatasusunan dan nilai val, dan anda mahu memadamkan elemen dalam tatasusunan yang sama dengan nilai val. Bagaimana untuk melakukannya?

Idea 1: Kaedah brutal

Kita boleh menggunakan dua untuk gelung Apabila melintasi elemen yang sama dengan nilai val, gerakkan keseluruhan elemen berikut ke hadapan untuk menutup elemen yang akan dipadamkan , tetapi pendekatan ini jelas mempunyai kerumitan masa yang terlalu tinggi.

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;
    }
}

Idea 2: Kaedah penunjuk berganda

Sediakan penunjuk cepat dan perlahan, masing-masing perlahan dan kedua-duanya bergerak bersama-sama Apabila penunjuk perlahan bertemu dengan elemen yang akan dipadamkan, ia berhenti dan menunggu untuk dipadamkan (tulis ganti); apabila penunjuk pantas mencapai elemen yang akan ditinggalkan, tetapkan elemen penunjuk pantas kepada penunjuk perlahan, dan kemudian kedua-dua penunjuk bergerak ke belakang pada masa yang sama sehingga pantas. penunjuk merentasi keseluruhan tatasusunan.

boleh difahami seperti ini: tentukan panjang baharu tatasusunan newLength, bermula dari 0, tentukan penunjuk pantas untuk melintasi tatasusunan dengan pantas, apabila pantas mencapai elemen yang akan ditinggalkan, ia bermakna elemen itu harus ditambahkan pada tatasusunan baharu (iaitu, ia ditambahkan pada subskrip newLength, yang bersamaan dengan bahagian tatasusunan sebelum newLength dianggap sebagai tatasusunan baharu yang akan dikembalikan, yang bersamaan dengan memasukkan elemen ke dalam tatasusunan baharu ini) .

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;
    }
}

Soalan yang disyorkan

1 Padamkan pendua dalam tatasusunan yang diisih

2 Gerakkan sifar

3 🎜>4. Segi empat bagi tatasusunan tertib

Banyak mata ujian tatasusunan biasa lain adalah berdasarkan dua titik ini. , anda boleh mula menjawab soalan.

Atas ialah kandungan terperinci Analisis contoh titik ujian frekuensi tinggi tatasusunan Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!