Program Javascript untuk mengira 1 dalam tatasusunan binari yang diisih

Kami mempunyai dua cara untuk mengira 1 dalam tatasusunan binari yang diisih. Yang pertama adalah untuk mengulangi tatasusunan dan mengira bilangan 1. Kaedah kedua ialah menggunakan algoritma carian binari untuk mencari kejadian pertama 1 dalam tatasusunan.

Adalah penting untuk ambil perhatian bahawa untuk menggunakan kaedah ini, tatasusunan mesti diisih.

Dalam catatan blog ini, kita akan membincangkan program JavaScript untuk mengira bilangan 1 dalam tatasusunan binari yang diisih. Kami juga akan melihat beberapa kes kelebihan dan teknik pengoptimuman untuk menjadikan program lebih cekap.

Pernyataan Masalah

Memandangkan tatasusunan binari diisih, tugasnya ialah mengira bilangan 1 dalam tatasusunan. Tatasusunan boleh dari sebarang saiz dan elemennya hanya boleh 0 atau 1.

Masuk

bin_array[] = {0, 0, 0,1,1,1}

Output

3

Kaedah 1

Pendekatan pertama yang terlintas di fikiran ialah mengulangi tatasusunan dan mengira bilangan 1.

• Memulakan pembolehubah kiraan untuk menyimpan nombor dalam tatasusunan.

• Lelaran pada tatasusunan dan semak setiap elemen. Jika elemen semasa adalah sama dengan 1, tambahkan pembilang.

Contoh

Walau bagaimanapun, kerumitan masa pendekatan ini ialah O(n), dengan n ialah saiz tatasusunan, memandangkan kita sedang melelakan keseluruhan tatasusunan sekali.

Ini boleh dioptimumkan dengan mengambil kesempatan daripada fakta bahawa tatasusunan disusun.

Kaedah 2

Untuk mencari contoh pertama 1 dalam tatasusunan, gunakan kaedah carian binari. Hanya tolak indeks 1 contoh pertama daripada jumlah bilangan item dalam tatasusunan untuk mendapatkan nombor 1.

• Dalam pelaksanaan ini, kami menggunakan teknik carian binari "kejadian pertama" untuk mencari tika pertama 0 dalam tatasusunan.

• Pembolehubah rendah dan tinggi pada mulanya ditetapkan kepada indeks pertama dan terakhir tatasusunan dengan sewajarnya.

• Bilangan item dalam tatasusunan juga dinyatakan sebagai nilai pembolehubah yang dipanggil firstOne, yang akan digunakan untuk merekodkan indeks contoh pertama nombor 1.

• Gelung while akan terus berjalan sehingga indeks rendah lebih besar atau sama dengan indeks tinggi. Selepas setiap lelaran, kami menentukan titik tengah julat semasa.

• Jika elemen tengah ialah 1, kemas kini pembolehubah firstOne dan alihkan indeks tinggi ke elemen terdahulu. Jika elemen pada titik tengah ialah 0, kita mengalihkan indeks bawah ke elemen seterusnya.

• Selepas gelung sementara selesai, kami menyemak sama ada pembolehubah pertama sepadan dengan nilai -1 tatasusunan. Jika ya, ini bermakna tiada 1 dalam tatasusunan, jadi 1 dikembalikan. Jika tidak, kembalikan dahuluSatu tolak arr.length.

Contoh

Kerumitan masa kaedah ini ialah O(log n), yang jauh lebih cekap daripada kaedah sebelumnya.

Dalam tutorial ini, kami membincangkan program JavaScript untuk mengira bilangan 1 dalam tatasusunan binari yang diisih.

Atas ialah kandungan terperinci Program Javascript untuk mengira 1 dalam tatasusunan binari yang diisih. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!