尋找與彼此距離最遠的元素的子集

我有一個面試問題，我似乎無法弄清楚。給定一個大小爲N的數組，找到大小爲k的子集，使子集中的元素彼此距離最遠。換句話說，最大化元素之間的最小配對距離。尋找與彼此距離最遠的元素的子集

Example: 

Array = [1,2,6,10] 
k = 3 

answer = [1,6,10]

bruteforce方法要求找到所有在運行時呈指數函數的大小爲k的子集。

我的一個想法是從數組中均勻分佈值。我的意思是

採取第1個和最後一個元素
找到（在這種情況下10-1）它們之間的區別，併除以K（（10-1）/ 3 = 3）
從兩端向內移動2個指針，挑選出你之前選擇的+/- 3的元素。所以在這種情況下，你從1和10開始，找到最接近的元素爲4和7.這將是6.

這是基於元素應該儘可能均勻分佈的直覺。我不知道如何證明它有效/無效。如果有人知道如何或有更好的算法，請分享。謝謝！

來源

2012-09-05 citysushi

這可以使用DP在多項式時間內求解。

正如你所提到的，第一步是對列表A進行排序。設X [i，j]是從第i個元素A中選擇j個元素的解。

現在，通過k < = i，X [i + 1，j + 1] = max（min（X [k，j]，A [i + 1] -A [k]））

我將離開初始化步驟並記憶子集步驟供您使用。

在你的榜樣（1,2,6,10），它的工作方式如下：

來源

2012-09-05 11:38:51 ElKamina

這是一個聰明的解決方案。我不能確定它是否萬無一失，但它對我的一些測試用例很有用。 – citysushi

實際上，我很確定這確實有效 – citysushi

我們如何找到實際的子集？我們得到了X [N] [i]中該子集的最大距離b/w元素，其中i是子集的大小？ –

我想，基本的想法是對的。您應該首先對數組進行排序，然後獲取第一個和最後一個元素，然後確定剩餘的元素。

我想不出一個多項式算法來解決這個問題，所以我會建議其中的一個選項。

一個是使用搜索算法，分支定界風格，因爲你手頭有一個很好的啓發：任何解決方案的上限是到目前爲止所選元素之間的最小尺寸，所以第一次猜測（如你所建議的，均勻間隔的單元格）可以給你一個很好的基線，這將有助於馬上修剪大部分分支。對於較小的值k，這將工作正常，但最壞的情況下性能爲O(N^k)。

另一種選擇是從相同的基線開始，爲它計算最小成對距離，然後嘗試改進它。假設你有一個最小距離爲10的子集，現在試着用11得到一個子集。這可以通過貪心算法輕鬆完成 - 選擇排序序列中的第一個項目，以便它與前一個項目之間的距離更大 - 或者等於你想要的距離。如果你成功了，如果你失敗了，嘗試進一步增加 - 沒有這樣的子集。

當數組較大時，後一種解決方案可能會更快，並且k也相對較大，但陣列中的元素相對較小。如果它們受某個值M的約束，則該算法將花費O(N*M)時間，或者具有小的改進O(N*log(M))，其中N是該數組的大小。

正如Evgeny Kluev在他的回答中所建議的，對於最大成對距離也有一個很好的上界，可以用於這兩種算法中的任何一種。所以後者的複雜性實際上是O(N*log(M/k))。

來源

2012-09-05 10:55:45 Qnan

我想您所設定的是有序的。如果沒有，我的答案會稍微改變。

Let's suppose you have an array X = (X1, X2, ..., Xn) 

Energy(Xi) = min(|X(i-1) - Xi|, |X(i+1) - Xi|), 1 < i <n 

j <- 1 
while j < n - k do 
    X.Exclude(min(Energy(Xi)), 1 < i < n) 
    j <- j + 1 
    n <- n - 1 
end while

來源

2012-09-05 11:43:55

 
$length = length($array); 
sort($array); //sorts the list in ascending order 
$differences = ($array << 1) - $array; //gets the difference between each value and the next largest value 
sort($differences); //sorts the list in ascending order 
$max = ($array[$length-1]-$array[0])/$M; //this is the theoretical max of how large the result can be 
$result = array(); 
for ($i = 0; i < $length-1; $i++){ 
    $count += $differences[i]; 
    if ($length-$i == $M - 1 || $count >= $max){ //if there are either no more coins that can be taken or we have gone above or equal to the theoretical max, add a point 
     $result.push_back($count); 
     $count = 0; 
     $M--; 
    } 
} 
return min($result)

對於非代碼的人：列表排序，發現每2個連續的元素之間的差異，那種名單（按升序排列），然後依次通過它總結了連續的值，直到您通過理論最大值或沒有足夠的元素剩餘;然後將該值添加到新數組並繼續，直到達到數組的末尾。然後返回新創建的數組的最小值。

雖然這只是一個快速草案。乍一看，這裏的任何操作都可以在線性時間內進行（基數排序）。

例如，1，4，7，100，200和M = 3，我們得到：

$differences = 3, 3, 93, 100 
$max = (200-1)/3 ~ 67 
then we loop: 
$count = 3, 3+3=6, 6+93=99 > 67 so we push 99 
$count = 100 > 67 so we push 100 
min(99,100) = 99

這是一個簡單的練習，將其轉換爲一組的解決方案，我離開了閱讀器（PS在閱讀完所有的書後，我一直想說：P）

來源

2012-09-08 08:12:56 chacham15

尋找與彼此距離最遠的元素的子集

回答

相關問題