首页  >  文章  >  web前端  >  Javascript 程序对已排序的二进制数组中的 1 进行计数

Javascript 程序对已排序的二进制数组中的 1 进行计数

WBOY
WBOY转载
2023-08-23 21:57:13728浏览

Javascript 程序对已排序的二进制数组中的 1 进行计数

我们有两种方法来计算已排序的二进制数组中的 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 进行计数的详细内容。更多信息请关注PHP中文网其他相关文章!

声明:
本文转载于:tutorialspoint.com。如有侵权,请联系admin@php.cn删除