rust 解法, 执行用时: 11 ms, 内存消耗: 4 MB, 提交时间: 2025-02-14 09:49:41

impl Solution {
    pub fn max_distance(mut price: Vec<i32>, k: i32) -> i32 {
        price.sort_unstable();

        let f = |d: i32| -> i32 {
            let mut cnt = 1;
            let mut pre = price[0]; // 先选一个最小的甜蜜度
            for &p in &price {
                if p >= pre + d { // 可以选
                    cnt += 1;
                    pre = p; // 上一个选的甜蜜度
                }
            }
            cnt
        };

        let mut left = 0;
        let mut right = (price.last().unwrap() - price[0]) / (k - 1) + 1;
        while left + 1 < right { // 开区间不为空
            // 循环不变量：
            // f(left) >= k
            // f(right) < k
            let mid = left + (right - left) / 2;
            if f(mid) >= k {
                left = mid;
            } else {
                right = mid;
            }
        }
        left // 最大的满足 f(left) >= k 的数
    }
}

python3 解法, 执行用时: 183 ms, 内存消耗: 30 MB, 提交时间: 2025-02-14 09:49:02

class Solution:
    def maxDistance(self, price: List[int], k: int) -> int:
        def check(d: int) -> bool:
            # 二分最小的 f(d+1) < k，从而知道最大的 f(d) >= k
            d += 1
            cnt = 1
            pre = price[0]  # 先选一个最小的甜蜜度
            for p in price:
                if p >= pre + d:  # 可以选
                    cnt += 1
                    pre = p  # 上一个选的甜蜜度
            return cnt < k

        price.sort()
        right = (price[-1] - price[0]) // (k - 1)
        return bisect_left(range(right), True, key=check)

cpp 解法, 执行用时: 40 ms, 内存消耗: 60.2 MB, 提交时间: 2025-02-14 09:48:09

class Solution {
public:
    int maxDistance(vector<int>& price, int k) {
        auto f = [&](int d) -> int {
            int cnt = 1, pre = price[0]; // 先选一个最小的甜蜜度
            for (int p : price) {
                if (p >= pre + d) { // 可以选
                    cnt++;
                    pre = p; // 上一个选的甜蜜度
                }
            }
            return cnt;
        };

        ranges::sort(price);
        int left = 0;
        int right = (price.back() - price[0]) / (k - 1) + 1;
        while (left + 1 < right) { // 开区间不为空
            // 循环不变量：
            // f(left) >= k
            // f(right) < k
            int mid = left + (right - left) / 2;
            (f(mid) >= k ? left : right) = mid;
        }
        return left; // 最大的满足 f(left) >= k 的数
    }
};

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;
    }
}