列表

详情

1552. 两球之间的磁力

在代号为 C-137 的地球上，Rick 发现如果他将两个球放在他新发明的篮子里，它们之间会形成特殊形式的磁力。Rick 有 n 个空的篮子，第 i 个篮子的位置在 position[i] ，Morty 想把 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 的篮子时最小磁力最大。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int maxDistance(vector<int>& position, int m) { } };

golang 解法, 执行用时: 156 ms, 内存消耗: 8.9 MB, 提交时间: 2022-12-10 13:05:11 

func maxDistance(position []int, m int) int {
	sort.Ints(position)
	left, right := 1, position[len(position)-1]
	for left < right {
		mid := (left + right + 1) >> 1
		if check(position, mid, m) {
			left = mid
		} else {
			right = mid - 1
		}
	}
	return left
}

func check(position []int, f, m int) bool {
	pre, cnt := position[0], 1
	for i := 1; i < len(position); i++ {
		if position[i]-pre >= f {
			cnt++
			pre = position[i]
		}
	}
	return cnt >= m
}

python3 解法, 执行用时: 736 ms, 内存消耗: 25.1 MB, 提交时间: 2022-12-10 13:04:25 

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:
        def check(x: int) -> bool:
            pre = position[0]
            cnt = 1
            for i in range(1, len(position)):
                if position[i] - pre >= x:
                    pre = position[i]
                    cnt += 1
            return cnt >= m

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

javascript 解法, 执行用时: 228 ms, 内存消耗: 52.1 MB, 提交时间: 2022-12-10 13:04:05 

/**
 * @param {number[]} position
 * @param {number} m
 * @return {number}
 */
const check = (x, position, m) => {
    let pre = position[0], cnt = 1;
    for (let i = 1; i < position.length; ++i) {
        if (position[i] - pre >= x) {
            pre = position[i];
            cnt += 1;
        }
    }
    return cnt >= m;
}
var maxDistance = function(position, m) {
    position.sort((x, y) => x - y);
    let left = 1, right = position[position.length - 1] - position[0], ans = -1;
    while (left <= right) {
        const mid = Math.floor((left + right) / 2); 
        if (check(mid, position, m)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return ans;
};

java 解法, 执行用时: 47 ms, 内存消耗: 56 MB, 提交时间: 2022-12-10 13:03:53 

class Solution {
    public int maxDistance(int[] position, int m) {
        Arrays.sort(position);
        int left = 1, right = position[position.length - 1] - 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;
    }

    public boolean check(int x, int[] position, int m) {
        int pre = position[0], cnt = 1;
        for (int i = 1; i < position.length; ++i) {
            if (position[i] - pre >= x) {
                pre = position[i];
                cnt += 1;
            }
        }
        return cnt >= m;
    }
}

上一题

© 2024 leetcode.cn