我們有兩種方法來計算已排序的二進位陣列中的 1。第一個是迭代數組併計算 1 的數量。第二種方法是使用二分查找演算法來找出陣列中第一次出現的 1。
要注意的是,為了使用這些方法,必須對陣列進行排序。
在這篇文章中,我們將討論一個 JavaScript 程式來計算已排序的二進位陣列中 1 的數量。我們還將研究一些邊緣情況和優化技術,以使程式更有效率。
問題陳述
給定一個已排序的二進位數組,任務是計算數組中 1 的數量。陣列可以是任意大小,元素只能是 0 或 1。
bin_array[] = {0, 0, 0,1,1,1}
3
首先想到的方法是迭代數組併計算 1 的數量。
初始化一個計數變數來儲存陣列中的個數。
迭代數組並檢查每個元素。如果目前元素等於 1,則增加計數器。
<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>
但是,這種方法的時間複雜度為 O(n),其中 n 是陣列的大小,因為我們要遍歷整個陣列一次。
這可以透過利用陣列已排序的事實來優化。
要尋找數組中 1 的第一個實例,請使用二分搜尋方法。只需從陣列中的項目總數中減去第一個 1 實例的索引即可得到 1 的數量。
在此實作中,我們使用「首次出現」二分搜尋技術來尋找陣列中 0 的第一個實例。
low 和 high 變數最初相應地設定為陣列的第一個和最後一個索引。
陣列中的項目數也被指定為名為firstOne的變數的值,該變數將用於記錄數字1的第一個實例的索引。
直到低索引大於或等於高索引,while 迴圈將繼續運作。每次迭代後,我們確定目前範圍的中點。
如果中間的元素為1,則更新firstOne變數並將高索引移至較早的元素。如果中間點的元素為 0,我們將低索引移到後續元素。
while 迴圈完成後,我們檢查第一個變數是否對應於陣列的 -1 值。如果是,則表示數組中沒有1,則傳回1。如果不是,則回傳firstOne 減去arr.length。
<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>
這種方法的時間複雜度是 O(log n),比之前的方法效率高很多。
在本教程中,我們討論了一個 JavaScript 程式來計算已排序的二進位數組中 1 的數量。
以上是Javascript 程式對已排序的二進位數組中的 1 進行計數的詳細內容。更多資訊請關注PHP中文網其他相關文章!