陣列中兩個數字之間的最小絕對差異

給定兩個數組A和B，我想從A和B中找到一個數字，以便兩個數字之間的絕對差值最小。陣列中兩個數字之間的最小絕對差異

例如

A = 1 2 9 
B= 4 5 6

答案：2,4-如Math.abs（2-4）= 2

來源

2011-03-13 TimeToCodeTheRoad

什麼編程語言？如果沒關係，請使用代碼高爾夫。 – 2011-03-13 15:59:20

排序的兩個陣列，然後它們迭代並行：對於每個項目在A，搜索通過線性搜索找到最接近的項目B。在B開始線性搜索，您停止前一項A。永遠記住迄今爲止發現的最小距離。

時間複雜度爲O（m log m + n log n）用於排序，O（m + n）用於最終搜索，其中m和n分別是A和B的長度。

來源

2011-03-13 15:55:58

假設陣列是（10,11,14）（4,6,8）在這種情況下，你不是一個O（n^2）算法。 – Algorithmist 2011-03-13 16:04:17

如果數組已經排序，則可能需要使用二分搜索。 – phimuemue 2011-03-13 16:04:39

@Algorithmist：不，搜索將是O（m + n），因爲您總是在上次停止的地方找到。你給的例子甚至會允許提早退出，因爲你將在'A'中的第一項消耗所有的'B'，所以你不必再看。 – 2011-03-13 16:27:11

檢查這，也許它給你的想法，所以你使其適應您的需求：

#define TOP 2147483647 
#define true 1 
#define false 0 


/* finds the minimum (absolute value) of vector vec */ 

void Vector_Min_Not_0(vector *vec, int *min, int *index) 
{ 
    int m, size, i, ind, aux; 

    size = vec->size; 
    m = TOP; 
    ind = -1; 
    for (i = 0; i < size; i++) 
    if (vec->p[i] != 0) 
     if (m > (aux = abs(vec->p[i]))) { 
    ind = i; 
    m = aux; 
     } 
    if (ind == -1) 
    *min = 1; 
    else 
    *min = m; 
    *index = ind; 
}

你叫它，具有這樣的結構：

typedef struct vector { 
    int size; 
    int *p; 
} vector; 

vector vec_A; 
int min, index, *p; 
Vector_Min_Not_0(&vec_A, &min, &index);

來源

2011-03-13 15:57:44 cMinor

它可以在O完成（nlogm + mlogm）= O（nlogm）：
（m是最小array`s長度）
假設B是較小的陣列

sort array B 
minimum = | A[0]-B[0] | 
for each a in A: 
binary search for a in B - return the closest numbers let the numbers be b1,b2 (*) 
if min{|b1-a|,|b2-a|} is smaller then the previous minimum - store it as the new minimum

（*）當你最接近數二進制搜索停止（或發現它，如果它存在的話）
首先檢查哪一個較小（A或B）將確保更好performance.-

來源

2011-03-13 16:01:45 amit

我假設數組中的數字是浮點數。在紅寶石：

def smaller_abs(array1, array2) 
    array1.product(array2).each_with_index do |ar,i| 
     if i==0 
     dif = (ar[0]-ar[1]).abs 
     pair = ar 
     next 
     end 
     pair = (ar[0]-ar[1]).abs > dif ? pair : ar 
    end 
    pair 
end

我不是算法大師，但必須工作（還沒有檢出）。希望我幫助！

來源

2011-03-13 16:21:01 Gerry

排序兩個數組
使用一些標籤來區分它們結合的兩個數字。例如A = 1 9 2 B = 5 4 6

排序後：

A = 1 2 9 B = 4 5 6

合併數組：C = 1A 2A 4B 5B 6B 9a

現在做一個線性搜索，找出不同標記的連續項之間的差異。答案：2a 4b。

來源

2012-02-10 22:40:51 surya

陣列中兩個數字之間的最小絕對差異

回答

相關問題