首頁  >  文章  >  web前端  >  使用另一個陣列最大化元素的 JavaScript 程序

使用另一個陣列最大化元素的 JavaScript 程序

WBOY
WBOY轉載
2023-09-05 20:09:111170瀏覽

使用另一个数组最大化元素的 JavaScript 程序

在本文中,我們將使用另一個陣列實作一個 JavaScript 程式來最大化元素。我們有兩個數組,必須從第二個數組中選取一些元素並替換第一個數組的元素。我們將看到實作將要討論的概念的完整程式碼。

問題簡介

在這個問題中,我們有兩個數組,我們必須使第一個數組的所有元素盡可能最大,或者簡單地我們必須使第一個數組的所有元素總和最大。我們可以從第二個陣列中選取元素,但重點是我們必須從第二個陣列中只選取一個元素一次,之後我們只能選取另一個元素。例如 -

我們有兩個陣列 -

Array1: 1 2 3 4 5 
Array2: 5 6 2 1 9

我們可以看到第二個陣列中的許多元素比第一個陣列中存在的元素更大。

我們可以選擇 9 代替 3,選擇 6 代替 2,選擇 5 代替 1。這使得最終的數組看起來像這樣 -

5 6 9 4 5 

我們將看到兩種方法,它們都透過對陣列和兩個指標進行排序來實現,但唯一的區別是我們將在哪裡選擇指標。

方法

我們已經看到了上面的範例,從中我們可以看到,我們可以將第一個陣列中的小元素與第二個陣列中的最大元素進行交換。

  • 第 1 步 - 首先,我們將按升序對兩個陣列進行排序,然後反轉第二個陣列以使其按降序排序。

  • 第 2 步 - 我們將維護兩個指向兩個陣列的第一個索引的指標。

  • 第 3 步 - 由於第一個元素指標將指向最小的數字,我們可以將該數字與第二個陣列的最大數字進行交易。

  • 第 4 步 - 在每次迭代中,我們將交換兩個陣列指標並增加指標。

  • 第 5 步 - 如果第一個陣列的目前索引的元素與第二個陣列的元素相比變得更大,那麼我們可以停止進一步的步驟。

  • 第 6 步 - 最後,我們將列印陣列的元素。

範例

// function to find the maximum array
function maximumArray(array1, array2){
   var len1 = array1.length
   var len2 = array2.length
   
   // sorting the elements of both arrays
   array1.sort()
   array2.sort()
   
   // reversing the arrays
   array1.reverse()
   array2.reverse()
   
   // traversing over the arrays
   var ptr1 = 0
   var ptr2 = 0
   var ptr3 = 0
   
   // creating new array to store the answer
   var ans = new Array(len1);
   while(ptr3 < len1){
      if(ptr2 == len2){
         while(ptr3 != len1){
            ans[ptr3] = array1[ptr1];
            ptr3++;
            ptr1++;
         }
      }
      else if(array1[ptr1] > array2[ptr2]){
         ans[ptr3] = array1[ptr1];
         ptr1++;
      } else {
         ans[ptr3] = array2[ptr2];
         ptr2++;
      }
      ptr3++;
   }
   console.log("The final array is: ")
   console.log(ans)
}
// declaring arrays
array1 = [1, 2, 4, 5, 3]
array2 = [5, 6, 2, 1, 9]

// calling the function
maximumArray(array1,array2)

時間與空間複雜度

上述程式碼的時間複雜度為 O(N*log(N)),其中 N 是給定數組的大小,這裡的對數因子是由於我們用來對數組進行排序的排序函數而產生的。

我們使用一個額外的陣列來儲存元素,這使得空間複雜度為 O(N),但是需要該陣列來儲存它的答案,可能會也可能不會被視為額外的空間。

直接排序方法

在先前的方法中,我們對數組的元素進行排序,然後使用兩個指標方法,但是有一個直接的方法,借助它我們可以簡單地做到這一點 -

  • 透過使用 new 關鍵字和 Array 關鍵字,我們將建立一個新數組,其大小為兩個給定數組的總和或長度。

  • 我們將兩個給定陣列的所有元素一一填入新陣列中。

  • 我們將對新建立的陣列進行排序,以按升序排列元素。

  • 所有最棒的元素都出現在最後,我們可以輕鬆獲得它們。

範例

// function to find the maximum array
function maximumArray(array1, array2){
   var len1 = array1.length
   var len2 = array2.length
   var ans = new Array(len1+len2);
   for(var i = 0; i<len1; i++){
      ans[i] = array1[i];
   }
   for(var i = 0; i< len2; i++){
      ans[i+len1] = array2[i];
   }
   ans.sort();
   for(var i = 0;i<len1;i++){
      array1[i] = ans[len2+len1-i-1];
   }
   console.log("The final array is: ")
   console.log(array1)
}

// declaring arrays
array1 = [1, 2, 4, 5, 3]
array2 = [5, 6, 2, 1, 9]
// calling the function
maximumArray(array1,array2)

時間與空間複雜度

上述程式碼的時間複雜度為 O(N*log(N)),其中 N 是給定數組的大小,這裡的對數因子是由於我們用來對數組進行排序的排序函數而產生的。

我們使用一個額外的陣列來儲存元素,這使得空間複雜度為 O(N)。

結論

在上面的教學中,我們已經實作了一個使用另一個陣列來最大化元素的 JavaScript 程式。我們有兩個數組,必須從第二個數組中選取一些元素並替換第一個數組的元素。我們已經看到兩種方法都使用排序的概念。一種具有兩個指標的方法需要 O(N*log(N)) 的時間和 O(1) 的空間,而另一種方法需要相同的時間但 O(N) 的空間。

以上是使用另一個陣列最大化元素的 JavaScript 程序的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除