LeetCode1552:球篮中的最大磁力(二分查找)

问题描述

在一个名为C-137的星球上，科学家Rick发现了一个有趣的现象：当他在自己新发明的篮子中放置两个球时，这两个球之间会产生一种特殊的磁力。Rick拥有n个篮子，每个篮子的位置由数组position表示。他的助手Morty想要在这n个篮子中放置m个球，目标是使任意两个球之间的最小磁力尽可能大。

已知两个球若分别位于位置x和y，则它们之间的磁力为|x - y|。给定一个整数数组position和一个整数m，任务是计算并返回能够实现的最大最小磁力值。

示例 1：
输入: position = [1,2,3,4,7], m = 3
输出: 3
解释: 将3个球分别放入位置1, 4, 7的篮子中，此时两球间的磁力分别为[3, 3, 6]，最小磁力为3。无法使最小磁力大于3。

示例 2：
输入: position = [5,4,3,2,1,1000000000], m = 2
输出: 999999999
解释: 将球放入位置1和1000000000的篮子中，可获得最大的最小磁力。

约束条件：
- 2 ≤ n ≤ 10^5
- 1 ≤ position[i] ≤ 10^9
- position中的所有整数互不相同
- 2 ≤ m ≤ position.length

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/magnetic-force-between-two-balls
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决方案

此问题可以通过二分查找来高效解决。基本思路如下：

• 首先对所有篮子的位置进行排序，这一步可以使用set容器自动完成。
• 然后使用二分查找技术来确定最佳的距离dis，即尝试找到一个距离值，使得可以在篮子中放置m个球，同时保证任意两球之间的距离至少为dis。
• 每次二分查找时，都需要检查当前的dis值是否可行，即是否可以放置m个球而保持至少dis的距离。如果可行，则尝试更大的距离；否则，减少距离值。

以下是C++代码实现：

class Solution {
private:
    set pos;
public:
    int maxDistance(vector& position, int m) {
        int l = 1, r = 1e9 + 1, dis, ans;
        for (auto i : position) pos.insert(i);
        while (l <= r) {
            dis = (l + r) / 2;
            if (canPutM(m, dis)) {
                ans = dis;
                l = dis + 1;
            } else {
                r = dis - 1;
            }
        }
        return ans;
    }
    bool canPutM(int m, int dis) {
        int count = 1, p = *pos.begin();
        auto it = pos.lower_bound(p + dis);
        while (it != pos.end() && count             ++count;
            p = *it;
            it = pos.lower_bound(p + dis);
        }
        return count == m;
    }
};

上述代码的时间复杂度主要取决于二分查找和排序操作，整体效率较高，适用于大规模数据处理。