我们有两种方法来计算已排序的二进制数组中的 1。第一个是迭代数组并计算 1 的数量。第二种方法是使用二分查找算法来查找数组中第一次出现的 1。
需要注意的是，为了使用这些方法，必须对数组进行排序。
在这篇博文中，我们将讨论一个 javascript 程序来计算已排序的二进制数组中 1 的数量。我们还将研究一些边缘情况和优化技术，以使程序更加高效。
问题陈述
给定一个已排序的二进制数组，任务是计算数组中 1 的数量。数组可以是任意大小，元素只能是 0 或 1。
输入 bin_array[] = {0, 0, 0,1,1,1}
输出 3
方法 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的第一个实例的索引。
直到低索引大于或等于高索引，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 进行计数的详细内容。