使用另一個數組最大化元素的 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) 的空間。