1552. Magnetic Force Between Two Balls

Problem

In the universe Earth C-137, Rick discovered a special form of magnetic force between two balls if they are put in his new invented basket. Rick has n empty baskets, the iᵗʰ basket is at position[i], Morty has m balls and needs to distribute the balls into the baskets such that the minimum magnetic force between any two balls is maximum.

Rick stated that magnetic force between two different balls at positions x and y is |x - y|.

Given the integer array position and the integer m. Return the required force.

https://leetcode.cn/problems/magnetic-force-between-two-balls/

Example 1:

Input: position = [1,2,3,4,7], m = 3
Output: 3
Explanation: Distributing the 3 balls into baskets 1, 4 and 7 will make the magnetic force between ball pairs [3, 3, 6]. The minimum magnetic force is 3. We cannot achieve a larger minimum magnetic force than 3.

Example 2:

Input: position = [5,4,3,2,1,1000000000], m = 2
Output: 999999999
Explanation: We can use baskets 1 and 1000000000.

Constraints:

• n == position.length
• 2 <= n <= 10⁵
• 1 <= position[i] <= 10⁹
• All integers in position are distinct.
• 2 <= m <= position.length

Test Cases

1
2

class Solution:
    def maxDistance(self, position: List[int], m: int) -> int:

1
2
3
4
5
6
7
8
9
10
11
12

import pytest

from solution import Solution


@pytest.mark.parametrize('position, m, expected', [
    ([1,2,3,4,7], 3, 3),
    ([5,4,3,2,1,1000000000], 2, 999999999),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, position, m, expected):
    assert sol.maxDistance(position.copy(), m) == expected

Thoughts

跟 1760. Minimum Limit of Balls in a Bag 的 二分法 思路差不多。因为 position 的值是离散的，想直接计算出结果比较困难，但可以快速验证给定的一个最小磁力是否能够达成。

对于给定的一个最小磁力值 force，如果能够摆得出来，那么更小的 force 也一定能摆得出来；如果摆不出来，那么更大的 force 也一定摆不出来。由此可以使用二分法找到分界点。

显然下界为 1。如果 position 中任意需要的位置都存在，那么上界为 (max{position} - min{position}) // (m - 1)（即最均匀地摆放）。

对于给定的 force，用贪心的办法从最左侧开始依次摆放每个球，看是否能把 m 个球全都摆好，时间复杂度 O(n)（需要事先对 position 排序）。

总的时间复杂度为 O(n * (log n + log p - log m))，其中 p 是 position 的最大值。额外的空间复杂度 O(1)。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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

        def check(force: int) -> bool:
            count = 1
            prev = position[0]
            for i in range(1, n):
                if position[i] - prev >= force:
                    prev = position[i]
                    count += 1

            return count >= m

        low = 1
        high = (position[-1] - position[0]) // (m - 1)
        while low <= high:
            mid = (low + high) >> 1
            if check(mid):
                low = mid + 1
            else:
                high = mid - 1

        return high

参考资料

• 本文引用

  • 1760. Minimum Limit of Balls in a Bag

许可协议

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

分享文章