数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
