如何使用分而治之算法在y軸上找到最佳線條？

Question

如果給出一組位置在y軸上的數字，我如何找到y軸上與該組數字的總體差異最小的位置。例如，如果給出數字1 8 3 6 2 7，它應該返回數字5，因爲它在15處的總差異最小。它必須是分而治之的方法。我不需要代碼我需要一個解釋。

Answer 1

讓我們以你的例子：1 8 3 6 2 7。我假設我們正在尋找一個整數的答案。

答案必須在最小和最大的數字之間。 0的差值總和大於1. 8的差值總和小於9.

用你的例子，結束界限是1和8.把它們加在一起，整數除以2.這給了我們4。或者，作爲替代方法，將所有數字相加併除以數量。以你爲例，總和爲27.整數除以6得到4.

4的差異之和是15.首先，讓我們回過頭來看看答案是否更小。

3的差異之和是15.所以，讓我們再次備份。

2的差異總和爲17.我們不必再往這個方向走。所以，從4.

向另一個方向5的差異總和是15.所以，讓我們繼續前進。

6的差異總和是15.再次，讓我們繼續前進。

的7差異的總和爲17

所以，最後的答案是3，4，5或6。我不知道你如何選擇一個是正確答案。

在這種情況下，我們可以檢查1到8之間的所有數字。但是當整數變得更大，比如1000時，這種分治法更快。

Answer 2

排序數字。你可以使用分而治之的算法。

然後最佳線位於中間的數字或兩個中間數字之間的任意位置，如果偶數的話。

請注意，在你的榜樣，3，4，5，6 所有有15

總差爲什麼這個工程：

如果你有n號碼上方的線和m數字在您的線下，並且您將線移動'x'，那麼總差異的變化爲m*x - n*x。所以如果你的線路有更多的數字，那麼你應該把它移動。如果它下面有更多的數字，那麼你應該把它移下來。當它具有相同的數字時，它是最優的。