匹配三個或更多數組中的最接近的數字

我有四個大小爲2^N的數組，其中N = 25。數組的元素由我的算法生成。這些是排序但包含數字。現在我必須採用array1的每個元素，並選擇array2，array3，array4的元素，使它們的總和應該最小（當我說sum時，我可以取a1 [k] + -a2 [j] + - a3 [m] + -A4 [T]。我認爲這是類似於K尺寸合併的問題。能否有人點到文學/實施/啓發式做同樣的。問候， Allahbaksh匹配三個或更多數組中的最接近的數字

來源

2012-04-04 Allahbaksh Asadullah

1.一個例子會非常有幫助。 2.您可以使用±符號。 – 2012-04-04 06:29:52

你所要求的單詞是微不足道的 - 從array2，3和4中取最小的元素，而不管array1的元素如何，那麼總和也是最小的。但我懷疑你想知道一些不同的東西。 – 2012-04-04 06:38:48

步驟1 對於數組1 [k]的，發現在數組2或ARRAY3數字或array4使得其模量是接近於ARRAY1 [K]。

eg . 
array1 = {1, 3, 67} 
array2 = {-31, 7, 47} 
array3 = {-1, 2, 10} 
array4 = {14, 15, 66} 

For array1[0] (ie. 1), the number closest to it is in array3 and its -1 as mod(-1) = 1

步驟2 然後在剩下的2個數組中，找到一對彼此更接近的數字。（再次考慮彈性模量）

eg . 
array2 = {-31, 7, 47} 
array4 = {14, 15, 66} 

Closest elements are 7 and 14 with -7 + 14 = 7.

最終你獲得分鐘（A1 [K] + -a2 [j]的+ - A4 [T] - A3 [M] +）所有4個陣列。

來源

2012-04-04 06:43:57

因此，對於array1中的1，這給出：1 - 1 - 7 + 14 = 7？但是你可以做得更好：1 + 7 + 10 - 14 = 4。 – Henrik 2012-04-04 07:15:20

這會以指數方式炸燬解決方案。我認爲這樣做的蠻力方式是把它放在for循環中。所以4個for循環用於四個陣列，當N增加時將需要巨大的計算能力。是否有適合KDM合併的啓發式算法？ – 2012-04-04 18:27:38

@亨利克：很好。我需要重新審視這個方法。 – 2012-04-04 18:32:03

我認爲這個問題可以在O（n）中解決，合併所有數組在聯合集所以第二個值將數組數。迭代通過它，並在每次迭代形式答案從4個值，在每一步計算所選數字之間的最大距離 - >最小化這個值。
初始化每個數組中數字最小的結果數組。

public Integer[] findClosest(int[][] unionSet, Integer[] result) { 

    for (int i = 0; i < unionSet.length; i++) { 
     int value = unionSet[i][0]; 
     int position = unionSet[i][1]; 
     int currentDistance = getDistance(result); 
     Integer[] temp = Arrays.copyOf(result, result.length); 
     temp[position] = value; 
     int newDistance = getDistance(temp); 
     if (newDistance <= currentDistance) { 
      result = temp; 
     } 
    } 
    return result; 
} 

private int getDistance(Integer[] result) { 
    int max = 0; 
    int min = 0; 
    for (int i = 1; i < result.length; i++) { 
     if (result[i] != null) { 
      if (result[i] > result[max]) { 
       max = i; 
      } 
      if (result[min] != null && result[i] < result[min]) { 
       min = i; 
      } 
     } 
    } 

    return Math.abs(result[max] - result[min]); 
}

來源

2012-08-21 18:28:14

匹配三個或更多數組中的最接近的數字

回答

相關問題