Leetcode-1552. 两球之间的磁力

链接

1552. 两球之间的磁力

题目

在代号为 C-137 的地球上,Rick 发现如果他将两个球放在他新发明的篮子里,它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子,第 i 个篮子的位置在 position[i] ,Morty 想把 m 个球放到这些篮子里,使得任意两球间 最小磁力 最大。

已知两个球如果分别位于 x 和 y ,那么它们之间的磁力为 |x - y| 。

给你一个整数数组 position 和一个整数 m ,请你返回最大化的最小磁力。

示例

Leetcode-1552. 两球之间的磁力

示例 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 的篮子时最小磁力最大。

说明

  • n == position.length
  • 2 <= n <= 10^5
  • 1 <= position[i] <= 10^9
  • 所有 position 中的整数 互不相同 。
  • 2 <= m <= position.length

思路

参考力扣官方题解

这题如果从正面推导具体的m个球的位置将会比较复杂,然而,我们可以逆向判断。

由于题目要求最大化最小磁力,因此我们要找的这个值是个临界值,

如果假设答案为ans,也就是最小磁力为ans,那么我们知道小于ans 的答案一定也合法(因为可当答案为ans时,各个球之间都尽量的远,而小于ans的话,各个球之间可以越来越近),而大于 ans 的值均不合法,因此我们可以对答案进行二分查找,直接逆向的寻找这个答案。

那么怎么判断合法还是不合法呢?也很简单,用贪心的思路,当答案为ans时,即两个球之间的距离最小为ans,为了尽量少的浪费空间,让每个球之间的距离都为≥ans的最小值,如果在篮子里能放得下≥m个球则合法,否则不合法。

我们在[left,right] 的区间查找,均值为mid,进行如下操作:

  • 如果当前的 mid 合法,则令 ans=mid,并将区间缩小为[mid+1,right];
  • 如果当前的mid 不合法,则将区间缩小为 [left,mid−1]。
  • 两个球之间最小的间距为1,最大的间距则为最后一个篮子的位置-最小的篮子的位置,这两个值即为初始的left和right。

C++ Code

class Solution {
public:
    bool check(int x, vector<int>& position, int m) {
        int pre = position[0], cnt = 1;
        for (int i = 1; i < position.size(); ++i) 
        {
            if (position[i] - pre >= x) 
            {
                pre = position[i];
                cnt += 1;
            }
        }
        return cnt >= m;
    }
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(), position.end());
        int left = 1, right = position.back() - position[0], ans = -1;
        while (left <= right) 
        {
            int mid = (left + right) / 2;
            if (check(mid, position, m)) 
            {
                ans = mid;
                left = mid + 1;
            } 
            else right = mid - 1;
        }
        return ans;
    }
};

上一篇:post与get,这两人到底神马区别??


下一篇:转】Maven学习总结(七)——eclipse中使用Maven创建Web项目