題目

標題和出處

標題：兩球之間的磁力

出處：1552. 兩球之間的磁力

難度

5 級

題目描述

要求

在代號為地球 C-137 的世界中，Rick 發(fā)現如果他將兩個球放在他新發(fā)明的籃子中，它們之間會形成特殊形式的磁力。Rick 有 $\text{n}$ 個空的籃子，第 $\text{i}$ 個籃子的位置在 $\text{position[i]}$，Morty 想把 $\text{m}$ 個球放到這些籃子中，使得任意兩球間的最小磁力最大。

Rick 聲明，兩個位于 $\text{x}$ 和 $\text{y}$ 的球之間的磁力為 $\text{|x?-?y|}$。

給定一個整數數組 $\text{position}$ 和一個整數 $\text{m}$，返回最小磁力的最大值。

示例

示例 1：

輸入：$\text{position?=?[1,2,3,4,7],?m?=?3}$
輸出：$\text{3}$
解釋：將 $\text{3}$ 個球分別放入位于 $\text{1}$、$\text{4}$ 和 $\text{7}$ 的三個籃子，兩球間的磁力分別為 $\text{[3,?3,?6]}$。最小磁力為 $\text{3}$。我們無法讓最小磁力大于 $\text{3}$。

示例 2：

輸入：$\text{position?=?[5,4,3,2,1,1000000000],?m?=?2}$
輸出：$\text{999999999}$
解釋：我們使用位于 $\text{1}$ 和 $\text{1000000000}$ 的籃子時最小磁力最大。

數據范圍

• $\text{n}=\text{position.length}$
• $\text{2}\le \text{n}\le {\text{10}}^{\text{5}}$
• $\text{1}\le \text{position[i]}\le {\text{10}}^{\text{9}}$
• 所有 $\text{position}$ 中的整數各不相同
• $\text{2}\le \text{m}\le \text{position.length}$

解法

思路和算法

由于兩個球之間的磁力等于兩個球之間的距離，因此為了得到最小磁力，需要計算最小距離。以下將最小磁力的最大值對應的最小距離的最大值稱為「臨界距離」。

當 $m$ 個球已經放入籃子時，最小距離一定是其中一對位置相鄰的球之間的距離，因此需要將數組 $\text{position}$ 升序排序，在排序后的籃子位置之間計算放入的球的最小距離。

如果任意兩個球之間的距離不超過臨界距離，則可以放入至少 $m$ 個球；如果存在兩個球之間的距離大于臨界距離，則不能放入 $m$ 個球。因此，這道題是二分查找判定問題，需要找到可以放入 $m$ 個球的最小距離的最大值。

用 $\text{low}$ 和 $\text{high}$ 分別表示二分查找的下界和上界。由于至少需要放入兩個球，當最小距離最大時每個球放在不同的籃子中，因此 $\text{low}$ 的初始值等于 $1$；由于最大距離為兩端的籃子之間的距離，因此 $\text{high}$ 的初始值等于 $\text{position}$ 中的最大值與最小值之差。

為了能放入 $m$ 個球，當最小距離確定時，應該在確保相鄰的球之間的距離不小于最小距離的前提下盡可能放入更多的球。因此，第一個球應該放到最左邊的籃子中，后面的每個球應該放到與前一個球的距離大于等于最小距離的最近的籃子中。根據該規(guī)則，遍歷排序后的數組 $\text{position}$，判斷每個球應該放到哪些籃子中，并計算放到籃子中的球的總數。

每次查找時，取 $\text{mid}$ 為 $\text{low}$ 和 $\text{high}$ 的平均數向上取整，將 $\text{mid}$ 作為最小距離，判斷是否可以將 $m$ 個球放到籃子中，執(zhí)行如下操作。

• 如果最小距離是 $\text{mid}$ 時可以將 $m$ 個球放到籃子中，則臨界距離大于等于 $\text{mid}$，因此在 $[\text{mid},\text{high}]$ 中繼續(xù)查找。

• 如果最小距離是 $\text{mid}$ 時不能將 $m$ 個球放到籃子中，則臨界距離小于 $\text{mid}$，因此在 $[\text{low},\text{mid}?1]$ 中繼續(xù)查找。

當 $\text{low}=\text{high}$ 時，查找結束，此時 $\text{low}$ 即為臨界距離。

得到臨界距離之后，臨界距離對應的磁力即為最小磁力的最大值。

代碼

class Solution {public int maxDistance(int[] position, int m) {Arrays.sort(position);int n = position.length;int low = 1, high = position[n - 1] - position[0];while (low < high) {int mid = low + (high - low + 1) / 2;if (canPutMBalls(position, m, mid)) {low = mid;} else {high = mid - 1;}}return low;}public boolean canPutMBalls(int[] position, int m, int force) {int count = 1;int prev = position[0];int n = position.length;for (int i = 1; i < n; i++) {if (position[i] - prev >= force) {count++;if (count == m) {return true;}prev = position[i];}}return false;}
}

復雜度分析

• 時間復雜度：$O(n\log (np))$，其中 $n$ 是數組 $\text{position}$ 的長度，$p$ 是數組 $\text{position}$ 中的最大值。排序需要 $O(n\log n)$ 的時間，排序之后需要執(zhí)行 $O(\log p)$ 次二分查找，每次二分查找需要 $O(n)$ 的時間遍歷數組 $\text{position}$ 判斷是否可以將 $m$ 個球放到籃子中，二分查找共需要 $O(n\log p)$ 的時間，因此時間復雜度是 $O(n\log n+n\log p)=O(n\log (np))$。

• 空間復雜度：$O(\log n)$，其中 $n$ 是數組 $\text{position}$ 的長度。排序需要 $O(\log n)$ 的遞歸調用?？臻g。