如何优化最优位置查找算法，解决大输入下的超时问题

问题描述 #

给定x轴上表示房屋的整数数组，房屋到x轴上某点x的距离定义为2*|house[i]-x|，需找出x轴范围[-10^9, 10^9]内，满足所有房屋到x的距离总和小于给定distance值的点的数量。

示例 #

• 输入：houses=[2,0,3,-4]，distance=22
• 有效点：{-1,0,1,2,3}，共5个

约束条件 #

• 房屋数组长度：1~10^5
• 房屋x坐标范围：[-10^9, 10^9]
• distance范围：0~10^15

现有代码问题 #

原代码思路为取中位数后向左右遍历验证，但每次验证需遍历所有房屋，时间复杂度为O(n*K)（K为有效点数量），面对大输入会超时，需要O(n log n)级别的低时间复杂度方案。

优化方案 #

核心思路 #

1. 简化问题：距离总和为2 * sum(|house[i]-x|)，因此只需找到x使得sum(|house[i]-x|) <= distance/2（记为target）。
2. 凸函数特性：排序后，sum(|house[i]-x|)是凸函数——x从左到右移动时，总和先递减至中位数区域，再递增。因此满足条件的x构成连续区间，只需找到区间的左右边界即可。
3. 快速计算总和：排序后预处理前缀和数组，结合二分查找，可在O(log n)时间内计算任意x对应的距离总和。

具体步骤 #

1. 对房屋数组排序，计算前缀和数组。
2. 用二分查找确定满足条件的左边界（最小x）和右边界（最大x）。
3. 计算区间内整数点的数量，同时裁剪到[-10^9, 10^9]范围内。

代码实现 #

import java.util.Arrays;
import java.util.List;

public class HouseDistanceSolver {
    public static void main(String[] args) {
        System.out.println(solve(Arrays.asList(2, 0, 3, -4), 22));
    }

    public static long solve(List<Integer> houses, long distance) {
        if (houses.isEmpty()) return 0;
        long target = distance / 2;
        int n = houses.size();
        long[] h = houses.stream().mapToLong(Integer::longValue).sorted().toArray();
        
        // 预处理前缀和
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + h[i];
        }

        // 找左边界：最小的x使得sum(|h[i]-x|) <= target
        long left = -1000000000L;
        long right = h[n - 1];
        long leftBound = h[n - 1];
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long sum = calculateSum(mid, h, prefixSum);
            if (sum <= target) {
                leftBound = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        // 找右边界：最大的x使得sum(|h[i]-x|) <= target
        left = h[0];
        right = 1000000000L;
        long rightBound = h[0];
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long sum = calculateSum(mid, h, prefixSum);
            if (sum <= target) {
                rightBound = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // 处理边界情况：如果没有满足条件的点
        if (calculateSum(leftBound, h, prefixSum) > target) {
            return 0;
        }

        // 裁剪到题目要求的范围
        leftBound = Math.max(leftBound, -1000000000L);
        rightBound = Math.min(rightBound, 1000000000L);

        return rightBound - leftBound + 1;
    }

    private static long calculateSum(long x, long[] h, long[] prefixSum) {
        int n = h.length;
        // 找到第一个大于等于x的位置
        int k = Arrays.binarySearch(h, x);
        if (k < 0) {
            k = -k - 1;
        }
        // 左边k个元素的距离和：x*k - sum(h[0..k-1])
        long leftSum = x * k - prefixSum[k];
        // 右边n-k个元素的距离和：sum(h[k..n-1]) - x*(n-k)
        long rightSum = (prefixSum[n] - prefixSum[k]) - x * (n - k);
        return leftSum + rightSum;
    }
}

复杂度分析 #

• 排序：O(n log n)
• 前缀和计算：O(n)
• 两次二分查找：每次O(log (2e9)) ≈ 30次，每次计算总和O(log n)，总时间O(log n)
• 整体时间复杂度：O(n log n)，符合大输入场景需求

内容的提问来源于stack exchange，提问作者Learner