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信箱登陸入口在哪裡

7814

Java教學

1646

CakePHP 教程

1402

Laravel 教程

1300

PHP教程

1236

Related knowledge

前端熱敏紙小票打印遇到亂碼問題怎麼辦？ Apr 04, 2025 pm 02:42 PM

前端熱敏紙小票打印的常見問題與解決方案在前端開發中，小票打印是一個常見的需求。然而，很多開發者在實...

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

JavaScript是現代Web開發的基石，它的主要功能包括事件驅動編程、動態內容生成和異步編程。 1)事件驅動編程允許網頁根據用戶操作動態變化。 2)動態內容生成使得頁面內容可以根據條件調整。 3)異步編程確保用戶界面不被阻塞。 JavaScript廣泛應用於網頁交互、單頁面應用和服務器端開發，極大地提升了用戶體驗和跨平台開發的靈活性。