Program Javascript untuk mengira 1 dalam tatasusunan binari yang diisih-tutorial js-php.cn

Program Javascript untuk mengira 1 dalam tatasusunan binari yang diisih

WBOY

Lepaskan： 2023-08-23 21:57:13

ke hadapan

702 orang telah melayarinya

Javascript 程序对已排序的二进制数组中的 1 进行计数

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}

Salin selepas log masuk

Output

Salin selepas log masuk

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

<html>
<body>
   <p id="result1"></p>
   <p id="result2"></p>
   <script>
      function count_num_of_Ones( bin_array,n) {
         let num_of_ones=0;
         for (let ind = 0; ind < n; ind++) {
            if(bin_array[ind]==1){
               num_of_ones++;
            }
         }
         return num_of_ones;
      }
      let bin_array = [0,0,0,1,1,1];
      let n = bin_array.length;
      document.getElementById("result1").innerHTML = "Original Array: " + JSON.stringify(bin_array);
      document.getElementById("result2").innerHTML = "Count of 1's in given array is " + count_num_of_Ones(bin_array,n)
   </script>
</body>
</html>

Salin selepas log masuk

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

<html>
<body>
   <p id="result1"></p>
   <p id="result2"></p>
   <script>
      function count_num_of_Ones(bin_arr,low,high) {
         var low = 0;
         var high = bin_arr.length - 1;
         var firstOne = -1;
         while (low <= high) {
            var mid = Math.floor((low + high) / 2);
            if (bin_arr[mid] == 1) {
               firstOne = mid;
               high = mid -1;
            } else {
               low = mid + 1;
            }
         }
         return firstOne == -1 ? 0 : bin_arr.length - firstOne;
      }
      let bin_array = [0,0,0,1,1,1,1];
      let n = bin_array.length;
      document.getElementById("result1").innerHTML = "Original Array: " + JSON.stringify(bin_array);
      document.getElementById("result2").innerHTML = "Count of 1's in given array is " + count_num_of_Ones(bin_array,n)
   </script>
</body>
</html>

Salin selepas log masuk

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!