資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究JavaScript 程式用於統計排序二進位制陣列中的 1
我們有兩種方法來統計排序二進位制陣列中的 1。第一種方法是遍歷陣列並統計 1 的數量。第二種方法是使用二分查詢演算法來查詢陣列中 1 的第一次出現。
需要注意的是，為了使用這些方法，陣列必須已排序。
在這篇博文中，我們將討論一個 JavaScript 程式，用於統計排序二進位制陣列中 1 的數量。我們還將研究一些邊緣情況和最佳化技術，以使程式更有效率。
問題陳述
給定一個排序的二進位制陣列，任務是統計陣列中 1 的數量。陣列可以是任意大小，並且元素只能是 0 或 1。
輸入
bin_array[] = {0, 0, 0,1,1,1}
輸出
3
方法 1
想到的第一種方法是遍歷陣列並統計 1 的數量。
初始化一個計數變數來儲存陣列中 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 是陣列的大小，因為我們遍歷了整個陣列一次。
可以透過利用陣列已排序的事實來最佳化這一點。
方法 2
要查詢陣列中 1 的第一個例項，請使用二分查詢方法。只需從陣列中 1 的第一個例項的索引減去陣列中的總專案數即可得出 1 的數量。
在此實現中，我們使用“第一次出現”二分查詢技術來查詢陣列中 0 的第一個例項。
low 和 high 變數最初分別設定為陣列的第一個和最後一個索引。
陣列中的專案數量也指定為名為 firstOne 的變數的值，該變數將用於記錄數字 1 的第一個例項的索引。
直到 low 索引大於或等於 high 值，while 迴圈將繼續執行。在每次迭代之後，我們確定當前範圍的中點。
如果中間的元素為 1，則更新 firstOne 變數並將 high 索引移動到前面的元素。如果中間的元素為 0，則將 low 索引移動到後續的元素。
while 迴圈完成後，我們檢查 firstOne 變數是否對應於陣列的 -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 的數量。
302 次檢視
