🔗 🟡 1552. Magnetic Force Between Two Balls 1920

tags: `Week Contest 202` `二分搜尋(Binary Search)` `排序(Sorting)`

題意

給定一個長度為 $n$ 的整數陣列 $\text{position}$ 和一個整數 $m$ ，其中 $\text{position}[i]$ 代表第 $i$ 個籃子的位置，現在需要把 $m$ 顆球放到這些籃子裡，使得任意兩球之間的 最小距離 最大。

若兩個球分別位於 $x$ 和 $y$ ，則它們之間的距離為 $|x - y|$ 。

返回最大的最小距離。

約束條件

$\text{position.length} = n$
$2 \leq n \leq 10^5$
$1 \leq \text{position}[i] \leq 10^9$
所有在 $\text{position}$ 中的整數都是不同的。
$2 \leq m \leq \text{position.length}$

思路：排序(Sorting) + 二分搜尋(Binary Search)

首先確定思路，要直接計算出最大的最小距離顯然是很困難的，但對於給定的距離 $d$ ，我們可以確定是否有 $m$ 顆球的距離都 $\geq d$ ，因此可以使用二分搜尋(Binary Search) 來找到最大的最小距離。

定義一個函數 check(d) 來檢查在待定距離 $d$ 內是否能放入 $m$ 顆球，使得任意兩球之間的距離至少為 $d$ 。

使用 $cnt$ 來記錄放置球的數量， $pre$ 來記錄前一個球的位置。
遍歷 $\text{position}$ $position$ 陣列中的每個元素 $\text{pos}$ $pos$
- 如果 $\text{pos} - \text{pre} \geq d$ ，代表可以放置球，則 $cnt$ 加一，並更新 $pre$ 為 $\text{pos}$ 。
最後返回 $cnt \geq m$ ，即是否可以放置 $m$ 顆球。

這裡使用左閉右閉區間進行二分搜尋，令 $left = 0$ ， $right = \text{position}[n-1] - \text{position}[0]$ ，在 $[left, right]$ 的範圍內進行二分搜尋，不斷調整左右範圍直到找到最大的最小距離為止。

根據定義的 check 函數，區間的左側為 $\text{True}$ ，而右側為 $\text{False}$ 。
如果 $\text{check}(mid) = \text{True}$ ，則將左範圍擴大到 $[mid+1, right]$ 。
如果 $\text{check}(mid) = \text{False}$ ，則將右範圍縮小到 $[left, mid-1]$ 。
當區間為空，即 $left > right$ 時，終止搜尋。

最終返回 $right$ ，即最大的最小距離。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n + n \log M) = \mathcal{O}(n \log (nM))$ $O (n lo g n + n lo g M) = O (n lo g (n M))$ ，其中 $n$ $n$ 為陣列 $\text{position}$ $position$ 的長度， $M$ $M$ 為 $\text{position}$ $position$ 的最大值。
- 對陣列 $\text{position}$ 進行排序需要 $\mathcal{O}(n \log n)$ 時間。
- 需要進行 $\log M$ 次二分搜尋，每次搜尋需要遍歷 $n$ 個元素來檢查是否可以放置 $m$ 顆球。
空間複雜度： $\mathcal{O}(1)$ ，忽略排序的空間複雜度。

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        n = len(position)
        position.sort()

        def check(d: int) -> bool:
            cnt = 1
            pre = position[0]
            for i in range(1, n):
                if position[i] - pre >= d:
                    cnt += 1
                    pre = position[i]
            return cnt >= m

        left, right = 0, position[-1] - position[0]
        while left <= right:
            mid = (left + right) // 2
            if check(mid):
                left = mid + 1
            else:
                right = mid - 1
        return right

class Solution {
public:
    int maxDistance(vector<int>& position, int m) {
        int n = position.size();
        sort(position.begin(), position.end());

        auto check = [&](int d) {
            int cnt = 1;
            int pre = position[0];
            for (int i = 1; i < n; ++i) {
                if (position[i] - pre >= d) {
                    cnt++;
                    pre = position[i];
                }
            }
            return cnt >= m;
        };

        int left = 0, right = position[n - 1] - position[0];
        while (left <= right) {
            int mid = (left + right) / 2;
            if (check(mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
};