Javascript 程式對已排序的二進位數組中的 1 進行計數-js教程-PHP中文網

首頁

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中文網其他相關文章！

陳述

本文轉載於：tutorialspoint。如有侵權，請聯絡admin@php.cn刪除

JavaScript和Web：核心功能和用例Apr 18, 2025 am 12:19 AM

JavaScript在Web開發中的主要用途包括客戶端交互、表單驗證和異步通信。 1)通過DOM操作實現動態內容更新和用戶交互；2)在用戶提交數據前進行客戶端驗證，提高用戶體驗；3)通過AJAX技術實現與服務器的無刷新通信。

了解JavaScript引擎：實施詳細信息Apr 17, 2025 am 12:05 AM

理解JavaScript引擎內部工作原理對開發者重要，因為它能幫助編寫更高效的代碼並理解性能瓶頸和優化策略。 1)引擎的工作流程包括解析、編譯和執行三個階段；2)執行過程中，引擎會進行動態優化，如內聯緩存和隱藏類；3)最佳實踐包括避免全局變量、優化循環、使用const和let，以及避免過度使用閉包。

Python vs. JavaScript：學習曲線和易用性Apr 16, 2025 am 12:12 AM

Python更適合初學者，學習曲線平緩，語法簡潔；JavaScript適合前端開發，學習曲線較陡，語法靈活。 1.Python語法直觀，適用於數據科學和後端開發。 2.JavaScript靈活，廣泛用於前端和服務器端編程。

Python vs. JavaScript：社區，圖書館和資源Apr 15, 2025 am 12:16 AM

Python和JavaScript在社區、庫和資源方面的對比各有優劣。 1)Python社區友好，適合初學者，但前端開發資源不如JavaScript豐富。 2)Python在數據科學和機器學習庫方面強大，JavaScript則在前端開發庫和框架上更勝一籌。 3)兩者的學習資源都豐富，但Python適合從官方文檔開始，JavaScript則以MDNWebDocs為佳。選擇應基於項目需求和個人興趣。

從C/C到JavaScript：所有工作方式Apr 14, 2025 am 12:05 AM

從C/C 轉向JavaScript需要適應動態類型、垃圾回收和異步編程等特點。 1）C/C 是靜態類型語言，需手動管理內存，而JavaScript是動態類型，垃圾回收自動處理。 2）C/C 需編譯成機器碼，JavaScript則為解釋型語言。 3）JavaScript引入閉包、原型鍊和Promise等概念，增強了靈活性和異步編程能力。

JavaScript引擎：比較實施Apr 13, 2025 am 12:05 AM

不同JavaScript引擎在解析和執行JavaScript代碼時，效果會有所不同，因為每個引擎的實現原理和優化策略各有差異。 1.詞法分析：將源碼轉換為詞法單元。 2.語法分析：生成抽象語法樹。 3.優化和編譯：通過JIT編譯器生成機器碼。 4.執行：運行機器碼。 V8引擎通過即時編譯和隱藏類優化，SpiderMonkey使用類型推斷系統，導致在相同代碼上的性能表現不同。