找到所有可能的數字組的最大值和最小值之間的最小差值

Question

有n數組的k大小。

a0[0],a0[1],......a0[k-1] 
a1[0],a1[1],......a1[k-1] 
. 
. 
. 
an-1[0],an-1[1], .... an-1[k-1] 

根本沒有重複，所有的數組排序。

現在，一組大小n通過從每個數組中隨機取任意值來構造。 ，例如一個這樣的組可以是{a0[0],a1[3],a2[2],.... an-1[k-1]}。

我的目標是找出所有可能集中的最小和最大元素，使得最小值和最大值之間的差值最小。

實施例（K = 3，N = 3）

[3 7 11] 
[1 12 15] 
[4 19 21] 

所以數學會有27組這樣

(3 1 4) (3 12 4) (3 15 4) 
(3 1 19) (3 12 19) (3 15 19) 
(3 1 21) (3 12 21) (3 15 21) 

(7 1 4) (7 12 4) (7 15 4) 
(7 1 19) (7 12 19) (7 15 19) 
(7 1 21) (7 12 21) (7 15 21) 

(11 1 4) (7 12 4) (11 15 4) 
(11 1 19) (7 12 19) (11 15 19) 
(11 1 21) (7 12 21) (11 15 21) 

計算所有這些組，我們可以得出這樣的結論的最小值和最大值後（3 1 4）是min（1）和max（4）之差爲全局最小值或最小值的集合。因此，我們將輸出3作爲全局最小差異和相應的對（3 4）。如果有多個全局最小值，則將它們全部打印出來。請提出更好的時間和空間複雜度的算法。我們不能採取暴力手段。

Answer 1

遍歷所有n * k元素。

說我們當前元素的值爲v。假設v是生成的n元組中的最小值，我們來計算最小差值。

二進制搜索的v在其他n - 1陣列（因爲他們排序，我們可以做到這一點）的位置，並注意減少它的最佳選擇那些大於或等於比v的最小元素的差異對於所有其他陣列。這正是二進制搜索給我們的。

一個例子：

[3 7 11] 
[1 12 15] 
[4 19 21] 

如果我們取v = 1第二陣列上，然後我們將在第二拾取3中的第一陣列上，和4。

複雜度爲O(N * K * N * log(N)) = O(N^2 * log(N) * K)。

Answer 2

如果我理解正確，您想要找到其元素中的最大差異全局最小的集合。 （我會稱該集合的範圍）

以k個集合開始，每個集合最初包含第一個數組中的一個元素。對於每個集合，最小值和最大值將等於元素本身。 以您的示例爲{3}，{7}和{11}。

然後你繼續前進到第二個數組。對於每個集合，您必須從該陣列中選取一個最小化新範圍的元素。理想情況下，你會選擇一個不增加範圍的元素（但現在不可能）。如果這是不可能的，選擇擴展您的設置兩個方向（加號和減號）的元素。例如，會給你{1-3}，{3-12}，{1-7}，{7-12}，{1-11}和{11-12}。從這些2k集合中，您可以刪除重疊的集合。例如，與集合{1-3}相比，集合{1-7}將始終具有更大或相等的範圍。您不需要調查{1-7}集。你最終得到集{1-3}和{11-12}。

繼續前進到第三個數組，再次選擇擴展每個集合的範圍儘可能小的元素。你最終得到{1-4}，{11-19}和{4-12}。然後，只需選擇範圍最低的那個。

Answer 3

考慮結果設置爲簡單的1XN陣列

[3] 
[1] 
[4] 

其中全球差爲3（最大4少最小爲1的）。

現在考慮Set的擴展定義，稱之爲MultiSet。 MultiSet是一個數組，其中每個元素包含一組有序的項目。

[3 7 11] 
[1 12 15] 
[4 19 21] 

我們可以計算出全球差異（稱之爲「成本」）由最大「最後」的每一行的值和最小「第一」的每一行的值之間的差異。在這種情況下，成本會21（max(11,15,21)）和1（min(3,1,4)）之間的差異，這是20

的方法現在將迭代的多集，直到我們達到使用以下算法最小成本：

• 標識具有最低值的行。如果此行只有一個元素，則繼續，否則請考慮從該行中刪除值低於其他行中的最低值的潛在成本降低。
• 標識具有最高值的行。如果該行只有元素，則繼續，否則考慮從該行中刪除高於其他行中的最高值的潛在成本降低。
• 刪除上面確定的值並繼續到下一個最高/最低項目。 -
• 如果最低和最高值都在單項行中，則成本已最小化。

爲了演示在給定的例子中，20的原始成本可以通過去除1的最低值（在這比任何其它的行最小低的多集的最低值）降低到18，或降低到通過從最後一行中除去最高值19和21（MultiSet中高於任何其他行的最大值的最高值，即15）。得到的多集是

[3 7 11] 
[1 12 15] 
[4] 

第二次迭代我們已經刪除12和15的成本降低到10

[3 7 11] 
[1] 
[4] 

第三和最後的迭代有我們刪除7和11到將成本降低到3.第三次迭代後，全局差異不能再最小化，從而達到解決方案。

複雜性？上被O爲界（N * M *的log（n）* K）

Answer 4

該算法的複雜度是O，從各行（N * K * logn）時間

僅選擇第一元件，並創建一個最小堆和一個最大的堆。

計算電流差（=頭（maxHeap）-head（minheap））

刪除minHeap的頭部（以及從maxHeap相應元素），並添加從相應的數組的下一個元素（對應於刪除元素）到minHeap和maxHeap。

重複該操作直到陣列中的所有元素都耗盡。

複雜性：您添加/刪除nk個元素，更新最多需要O（n）個時間。所以複雜性是O（nklogn）。

注意：這不完全是你的股票堆。 minHeap包含指向maxHeap中相同元素的指針，反之亦然。當您從minHeap中刪除元素時，您可以找到指向maxHeap的鏈接並將其刪除。此外，無論何時某個元素的位置發生更改，都會對另一個堆中的鏈接進行適當更改。

Answer 5

代碼：

private static ElementData calcMin(int[] n1Arr, int[] n2Arr, int[] n3Arr) { 

    ElementData data = new ElementData();// added just to know which two elements algo has picked 

    int[] mixArr = { n1Arr[0], n2Arr[0], n3Arr[0] }; 
    Arrays.sort(mixArr); 
    int minValue = mixArr[2] - mixArr[0]; 

    data.setMinValue(minValue); 
    data.setHighValue(mixArr[2]); 
    data.setLowValue(mixArr[0]); 

    int tempValue = 0; 
    for (int n1 : n1Arr) { 

     for (int n2 : n2Arr) { 

      for (int n3 : n3Arr) { 

       int[] mixArr1 = { n1, n2, n3 }; 
       Arrays.sort(mixArr1); 

       tempValue = mixArr1[2] - mixArr1[0]; 
       if (minValue > tempValue) { 
        minValue = tempValue; 

        data = new ElementData(); 
        data.setMinValue(minValue); 
        data.setHighValue(mixArr1[2]); 
        data.setLowValue(mixArr1[0]); 
       } 
      } 
     } 
    } 
    return data; 
}