大小為二的組之間的最大差值的 JavaScript 程式

---

在這個程式中，我們得到一個偶數長度的整數陣列，因為我們知道這裡我們必須組成大小為二的組。我們必須從使用陣列元素組成的這些組中，選擇其中兩個組，以便找到這兩個組之間的最大差值，並且我們必須返回該最大差值，這將在下面的文章中看到。

問題介紹

在給定的問題中，我們必須找到大小為二的組之間的最大差值。這意味著我們得到了一個偶數長度的陣列，並且我們必須組成大小為二的組。由於我們必須返回組之間的最大差值，因此我們必須找到一個和最大的組和一個和最小的組，並返回它們的差值。

示例 1

我們得到一個大小為 num 的陣列，

Input:
Num = 4
Array = {5, 1, 6, 7}
Output: 7 

這裡形成的組將是 {5,1} 和 {6,7}，即分別為 6 和 13，並且和最大組與和最小組之間的差值為 13 - 6 等於 7。

示例 2

Input:
Num =  6
Array = {3, 1, 2, 4, 5, 6}
Output: 8

這裡形成的組將是 {1,2}，{3,4} 和 {5,6}，即分別為 3、7 和 11，並且和最大組與和最小組之間的差值為 11 - 3 等於 8。

方法 1：暴力方法

在這種方法中，我們建立每種可能的組組合，並將每組組合中和最大組與和最小組之間的差值與其他組合進行比較。

總共有 n*(n-1)/2 種分組（nC2）。

時間複雜度：O(n^3)，因為它需要 O(n^2) 來構造組，並且需要 O(n) 來檢查每個組。

方法 2：使用排序函式

在這種方法中，我們首先使用排序函式對陣列進行排序，因為我們知道我們需要兩個組的和最大值和最小值，所以我們將排序陣列的第一個和第二個值加起來得到最小和，並將排序陣列的最後一個和倒數第二個值加起來得到最大和，然後返回這兩個和的差值。現在讓我們來看一個例子。

示例

使用排序函式查詢兩個組之間最大差值的 JavaScript 程式。

function calMaxDiff( array , num){
   //sorting an array using the sort function
   array.sort();
   let highestVal = array[num - 1] + array[num - 2];
   let lowestVal =  array[0] + array [1];
   return (Math.abs(highestVal - lowestVal));
}
let num = 6;
let array = [3, 1, 2, 4, 5, 6];
console.log("Maximum Difference: " + calMaxDiff( array, num ));

時間和空間複雜度

上面程式碼的時間複雜度為 O(NlogN)，因為這裡我們使用了排序函式。這裡 N 是陣列的大小。

上面程式碼的空間複雜度為 O(1)。

方法 3：透過查詢兩個最大值和兩個最小值

在這種方法中，我們必須找到陣列中的第一個和第二個最大值，並找到陣列中的第一個和第二個最小值。

示例

查詢兩個組之間最大差值的 JavaScript 程式。

function calMaxDiff( array , num){
   let firstMin = Math.min.apply(Math,array);;
   let secondMin = Number.MAX_VALUE;
   for(let i = 0; i < num ; i ++) {
      // If array[i] is not equal to first min
      if (array[i] != firstMin)
         secondMin = Math.min(array[i],secondMin);
   }
   let firstMax = Math.max.apply(Math,array);;
   let secondMax = Number.MIN_VALUE;
   for (let i = 0; i < num ; i ++){
      // If array[i] is not equal to first max
      if (array[i] != firstMax)
         secondMax = Math.max( array[i], secondMax);
   }
   return Math.abs(firstMax+secondMax-firstMin-secondMin);
}
let num = 6;
let array = [3, 1, 2, 4, 5, 6];
console.log("Maximum Difference: " + calMaxDiff( array, num ));

時間和空間複雜度

上面程式碼的時間複雜度為 O(N)，因為這裡我們只遍歷陣列以查詢最大值和最小值。這裡 N 是陣列的大小。

上面程式碼的空間複雜度為 O(1)。

結論

在本文中，我們討論了查詢大小為二的組之間的最大差值。這裡我們討論了三種解決問題的方法。第一種方法的時間複雜度為 O(N^3)，接下來一種方法的時間複雜度為 O(N*log(N))，但最後一種方法的時間複雜度為 O(N)。