hujung hadapan web
tutorial js
Program Javascript untuk mengira 1 dalam tatasusunan binari yang diisih
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
<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>
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>
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!
Alat AI Hot
Undresser.AI Undress
Apl berkuasa AI untuk mencipta foto bogel yang realistik
AI Clothes Remover
Alat AI dalam talian untuk mengeluarkan pakaian daripada foto.
Undress AI Tool
Gambar buka pakaian secara percuma
Clothoff.io
Penyingkiran pakaian AI
Video Face Swap
Tukar muka dalam mana-mana video dengan mudah menggunakan alat tukar muka AI percuma kami!
Artikel Panas
Alat panas
Notepad++7.3.1
Editor kod yang mudah digunakan dan percuma
SublimeText3 versi Cina
Versi Cina, sangat mudah digunakan
Hantar Studio 13.0.1
Persekitaran pembangunan bersepadu PHP yang berkuasa
Dreamweaver CS6
Alat pembangunan web visual
SublimeText3 versi Mac
Perisian penyuntingan kod peringkat Tuhan (SublimeText3)
Topik panas
1393
52
1207
24
Apa yang perlu saya lakukan jika saya menghadapi percetakan kod yang dihiasi untuk resit kertas terma depan?
Apr 04, 2025 pm 02:42 PM
Soalan dan penyelesaian yang sering ditanya untuk percetakan tiket kertas terma depan dalam pembangunan front-end, percetakan tiket adalah keperluan umum. Walau bagaimanapun, banyak pemaju sedang melaksanakan ...
Siapa yang dibayar lebih banyak Python atau JavaScript?
Apr 04, 2025 am 12:09 AM
Tidak ada gaji mutlak untuk pemaju Python dan JavaScript, bergantung kepada kemahiran dan keperluan industri. 1. Python boleh dibayar lebih banyak dalam sains data dan pembelajaran mesin. 2. JavaScript mempunyai permintaan yang besar dalam perkembangan depan dan stack penuh, dan gajinya juga cukup besar. 3. Faktor mempengaruhi termasuk pengalaman, lokasi geografi, saiz syarikat dan kemahiran khusus.
Demystifying JavaScript: Apa yang berlaku dan mengapa penting
Apr 09, 2025 am 12:07 AM
JavaScript adalah asas kepada pembangunan web moden, dan fungsi utamanya termasuk pengaturcaraan yang didorong oleh peristiwa, penjanaan kandungan dinamik dan pengaturcaraan tak segerak. 1) Pengaturcaraan yang didorong oleh peristiwa membolehkan laman web berubah secara dinamik mengikut operasi pengguna. 2) Penjanaan kandungan dinamik membolehkan kandungan halaman diselaraskan mengikut syarat. 3) Pengaturcaraan Asynchronous memastikan bahawa antara muka pengguna tidak disekat. JavaScript digunakan secara meluas dalam interaksi web, aplikasi satu halaman dan pembangunan sisi pelayan, sangat meningkatkan fleksibiliti pengalaman pengguna dan pembangunan silang platform.
Bagaimana untuk menggabungkan elemen array dengan ID yang sama ke dalam satu objek menggunakan JavaScript?
Apr 04, 2025 pm 05:09 PM
Bagaimana cara menggabungkan elemen array dengan ID yang sama ke dalam satu objek dalam JavaScript? Semasa memproses data, kita sering menghadapi keperluan untuk mempunyai id yang sama ...
Bagaimana untuk mencapai kesan menatal paralaks dan kesan animasi elemen, seperti laman web rasmi Shiseido?
atau:
Bagaimanakah kita dapat mencapai kesan animasi yang disertai dengan menatal halaman seperti laman web rasmi Shiseido?
Apr 04, 2025 pm 05:36 PM
Perbincangan mengenai realisasi kesan animasi tatal dan elemen Parallax dalam artikel ini akan meneroka bagaimana untuk mencapai yang serupa dengan laman web rasmi Shiseido (https://www.shiseido.co.jp/sb/wonderland/) ... ...
Adakah JavaScript sukar belajar?
Apr 03, 2025 am 12:20 AM
Pembelajaran JavaScript tidak sukar, tetapi ia mencabar. 1) Memahami konsep asas seperti pembolehubah, jenis data, fungsi, dan sebagainya. 2) Pengaturcaraan asynchronous tuan dan melaksanakannya melalui gelung acara. 3) Gunakan operasi DOM dan berjanji untuk mengendalikan permintaan tak segerak. 4) Elakkan kesilapan biasa dan gunakan teknik debugging. 5) Mengoptimumkan prestasi dan mengikuti amalan terbaik.
Bagaimana untuk melaksanakan fungsi seretan panel dan drop pelarasan yang serupa dengan vscode dalam pembangunan front-end?
Apr 04, 2025 pm 02:06 PM
Terokai pelaksanaan fungsi seretan panel dan drop panel seperti VSCode di bahagian depan. Dalam pembangunan front-end, bagaimana untuk melaksanakan vscode seperti ...
Perbezaan dalam Konsol.Log Output Result: Mengapa kedua -dua panggilan berbeza?
Apr 04, 2025 pm 05:12 PM
Perbincangan mendalam mengenai punca-punca utama perbezaan dalam output konsol.log. Artikel ini akan menganalisis perbezaan hasil output fungsi Console.log dalam sekeping kod dan menerangkan sebab -sebab di belakangnya. � ...
