C语言重构【1552】两球之间的磁力

雨点打透心脏的1/2处 2022-10-28 13:27 17阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 m 个球放到这些篮子里，使得任意两球间 最小磁力 最大。
    
    已知两个球如果分别位于 x 和 y ，那么它们之间的磁力为 |x - y| 。
    
    给你一个整数数组 position 和一个整数 m ，请你返回最大化的最小磁力。
    
     
    
    示例 1：

![在这里插入图片描述][20210206142445447.png]

输入：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

#### 方案： ####

*  二分法

class Solution
    { 
    public:
        //检查该gap是否满足
        bool check(int gap, vector<int> &position, int m)
        { 
            int res = 1, last = position[0], len = position.size();
            for (int i = 0; i < len; i++)
            { 
                if (position[i] >= last + gap)
                { 
                    last = position[i];
                    res++;
                }
            }
            return res >= m;
        }
        int maxDistance(vector<int> &position, int m)
        { 
            sort(position.begin(), position.end());
            //如果m>2，比如3
            int len = position.size();
            //题目所给gap=1是一定满足要求的
            int left = 0, right = position[len - 1] - position[0];
            int mid;
            int res = 1;
           
            while (left <= right)
            { 
                mid = (left + right) / 2;
                if (check(mid, position, m))
                { 
                    //可以，则往大缩小范围
                    res = mid;
                    left = mid + 1;
                }
                else
                    right = mid - 1;
            }
            return res;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(nlogn)
 *  空间复杂度：O(logn)，调用了logn次check

[Git]: https://github.com/ch98road/leetcode
[20210206142445447.png]: /images/20221024/38c44d69ae6847d680bd27f540ca4a40.png