題目

標(biāo)題和出處

標(biāo)題：兩球之間的磁力

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

難度

5 級(jí)

題目描述

要求

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

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

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

示例

示例 1：

輸入：$\text{position?=?[1,2,3,4,7],?m?=?3}$
輸出：$\text{3}$
解釋：將 $\text{3}$ 個(gè)球分別放入位于 $\text{1}$、$\text{4}$ 和 $\text{7}$ 的三個(gè)籃子，兩球間的磁力分別為 $\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}$ 的籃子時(shí)最小磁力最大。

數(shù)據(jù)范圍

• $\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}$ 中的整數(shù)各不相同
• $\text{2}\le \text{m}\le \text{position.length}$

解法

思路和算法

由于兩個(gè)球之間的磁力等于兩個(gè)球之間的距離，因此為了得到最小磁力，需要計(jì)算最小距離。以下將最小磁力的最大值對(duì)應(yīng)的最小距離的最大值稱為「臨界距離」。

當(dāng) $m$ 個(gè)球已經(jīng)放入籃子時(shí)，最小距離一定是其中一對(duì)位置相鄰的球之間的距離，因此需要將數(shù)組 $\text{position}$ 升序排序，在排序后的籃子位置之間計(jì)算放入的球的最小距離。

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

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

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

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

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

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

當(dāng) $\text{low}=\text{high}$ 時(shí)，查找結(jié)束，此時(shí) $\text{low}$ 即為臨界距離。

得到臨界距離之后，臨界距離對(duì)應(yīng)的磁力即為最小磁力的最大值。

代碼

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;}
}

復(fù)雜度分析

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

• 空間復(fù)雜度：$O(\log n)$，其中 $n$ 是數(shù)組 $\text{position}$ 的長(zhǎng)度。排序需要 $O(\log n)$ 的遞歸調(diào)用棧空間。