算法：找出陣列中兩個元素之間最接近的差異

您有一個數組和一個目標。找出數組中兩個元素的區別。這種差異應該最接近目標。算法：找出陣列中兩個元素之間最接近的差異

（即，找到i, j使得（array[i]- array[j]）應該是最接近目標）

嘗試： 我使用order_map（C++哈希表）來存儲陣列中的每個元素。這將是O（n）。然後，我將有序元素輸出到一個新的數組（這是排序增加的數字）。

接下來，我使用了兩個指針。

int mini = INT_MAX, a, b; 
for (int i=0, j = ordered_array.size() -1 ; i <j;) { 
    int tmp = ordered_array[i] - ordered_array[j]; 
    if (abs(tmp - target) < mini) { 
      mini = abs(tmp - target); 
      a = i; 
      b = j; 
     } 
    if (tmp == target) return {i,j}; 
    else if (tmp > target) j --; 
    else i ++; 
} 
return {a,b};

問：

是我的算法仍然在O（n）的運行？

來源

2017-07-26 wrek

兩個因素的差異，應該是最接近目標 – wrek

不管你做什麼，一般你需要的n log n至理清，除非你使用的算法類似基數排序這需要對輸入的範圍優勢，但我我不知道他們是O（n）算法 –

我想知道是否有O（n）算法來解決這個問題？ – wrek

如果數組已經排序，則存在O（n）算法：讓兩個指針向上滑過數組，每當指向元素之間的差異小於目標時，增加上一個，每當它大於目標時，增加下一個。在這樣做的同時，追蹤迄今爲止發現的最佳結果。

當您到達數組的末尾時，找到總體最佳結果。

很容易看出這真的是O（n）。兩個指針只會向上移動，每移動一個指針，數組就有n個元素。所以在最多2n步後，這將停止。如前所述，如果您需要首先對數組進行排序，則需要O（n log n）努力進行排序（除非您可以使用某些基數排序或計數排序）。

來源

2017-07-26 05:04:34 Henry

您的搜索階段是線性的。雙指針的方法是相同的：

Make a copy of sorted array 
Add `target` to every entry (shift values up or down) (left picture) 
Invert shifted array indexing (right picture) 
Walk through both arrays in parallel, checking for absolute difference 
All stages are linear (and inverting is implicit in your code)

附： C++哈希映射是否有序？我懷疑。 O（nlogn）排序（除了計數或基數排序等特殊方法外）

來源

2017-07-26 04:26:50 MBo

算法：找出陣列中兩個元素之間最接近的差異

回答

相關問題