Javascript 程序对已排序的二进制数组中的 1 进行计数-js教程-PHP中文网

输入

输出

方法2

示例

首页

web前端

js教程

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

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB

Aug 23, 2023 pm 09:57 PM

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

我们有两种方法来计算已排序的二进制数组中的 1。第一个是迭代数组并计算 1 的数量。第二种方法是使用二分查找算法来查找数组中第一次出现的 1。

需要注意的是，为了使用这些方法，必须对数组进行排序。

在这篇博文中，我们将讨论一个 JavaScript 程序来计算已排序的二进制数组中 1 的数量。我们还将研究一些边缘情况和优化技术，以使程序更加高效。

问题陈述

给定一个已排序的二进制数组，任务是计算数组中 1 的数量。数组可以是任意大小，元素只能是 0 或 1。

输入

 bin_array[] = {0, 0, 0,1,1,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的第一个实例的索引。
直到低索引大于或等于高索引，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中文网其他相关文章！

本站声明

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

热AI工具

Undresser.AI Undress

人工智能驱动的应用程序，用于创建逼真的裸体照片

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

免费脱衣服图片

Clothoff.io

AI脱衣机

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸！

显示更多

热工具

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

中文版，非常好用

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

显示更多

热门话题

gmail邮箱登陆入口在哪里

7739

Java教程

1643

CakePHP 教程

1397

Laravel 教程

1290

PHP教程

1233

显示更多

Related knowledge

前端热敏纸小票打印遇到乱码问题怎么办？ Apr 04, 2025 pm 02:42 PM

前端热敏纸小票打印的常见问题与解决方案在前端开发中，小票打印是一个常见的需求。然而，很多开发者在实...

神秘的JavaScript：它的作用以及为什么重要 Apr 09, 2025 am 12:07 AM

JavaScript是现代Web开发的基石，它的主要功能包括事件驱动编程、动态内容生成和异步编程。1)事件驱动编程允许网页根据用户操作动态变化。2)动态内容生成使得页面内容可以根据条件调整。3)异步编程确保用户界面不被阻塞。JavaScript广泛应用于网页交互、单页面应用和服务器端开发，极大地提升了用户体验和跨平台开发的灵活性。