算法基础算法

一维散点到定点的距离之和

字数统计: 1.4k字   |   阅读时长: 5分
,

摘要: 前缀和的应用：推导后得到含区间和的表达式

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

给定 n 个点，然后问这 n 个给定点到某个点的距离之和。要算出这个值，最直接的做法是先计算 n 个给定点与查询点之间的距离，然后将其求和，一般可以 $O(n)$ 解决。

但如果要很多次查询一个点与 n 个给定点的距离之和，直觉上不应该每次查询都要走上述的 $O(n)$ 计算过程，因为对于 $m$ 次查询，总时间复杂度就来到 $O(mn)$。

那么我们就要考虑是否有某种预处理的方式，使得可以以较低的时间复杂度相应查询，最终预处理和相应查询的总时间复杂度低于 $O(mn)$。

本文我们研究这个问题的一维版本，即给定数轴上的 n 个点 $x_{i}, i=1,2,\cdots,n$，然后进行 $m$ 次查询，每次查询输入一个点 $y_{j},j=1,2,\cdots,m$，返回距离之和 $\sum\limits_{i=1}\limits^{n}|x_{i} - y_{j}|$。

需要推公式来整理思路，最终发现可以预处理前缀和来解决。通过这个问题的解决可以看到，由于很多问题最终答案归结为和式，所以前缀和可以解决的问题很多，但是有时需要推推公式才能发现用前缀和可以解决。

题目

给你一个正整数数组 nums 。

同时给你一个长度为 m 的整数数组 queries 。第 i 个查询中，你需要将 nums 中所有元素变成 queries[i] 。你可以执行以下操作 任意 次：

  • 将数组里一个元素 增大 或者 减小 1 。

请你返回一个长度为 m 的数组 answer ，其中 answer[i]是将 nums 中所有元素变成 queries[i] 的 最少 操作次数。

注意，每次查询后，数组变回最开始的值。

提示：

1
2
3
4
n == nums.length
m == queries.length
1 <= n, m <= 1e5
1 <= nums[i], queries[i] <= 1e9

示例 1：
输入：nums = [3,1,6,8], queries = [1,5]
输出：[14,10]
解释：第一个查询，我们可以执行以下操作：

  • 将 nums[0] 减小 2 次，nums = [1,1,6,8] 。
  • 将 nums[2] 减小 5 次，nums = [1,1,1,8] 。
  • 将 nums[3] 减小 7 次，nums = [1,1,1,1] 。
    第一个查询的总操作次数为 2 + 5 + 7 = 14 。
    第二个查询，我们可以执行以下操作：
  • 将 nums[0] 增大 2 次，nums = [5,1,6,8] 。
  • 将 nums[1] 增大 4 次，nums = [5,5,6,8] 。
  • 将 nums[2] 减小 1 次，nums = [5,5,5,8] 。
  • 将 nums[3] 减小 3 次，nums = [5,5,5,5] 。
    第二个查询的总操作次数为 2 + 4 + 1 + 3 = 10 。

示例 2：
输入：nums = [2,9,6,3], queries = [10]
输出：[20]
解释：我们可以将数组中所有元素都增大到 10 ，总操作次数为 8 + 1 + 4 + 7 = 20 。

题解

算法：前缀和

将 nums 中的元素视为数轴上的 n 个点 $x_{1},\cdots,x_{n}$，queries 中的 m 个查询要求的实际上是查询点 $y_{j},j=1,\cdots,m$ 到 n 个给定点的距离之和。

考虑其中的一次查询 $y_{j}$，答案如下：

首先考虑一种简单的情况，即 $\max(x_{i}) \leq y_{j}$，那么 $q(j)$ 的绝对值可以去掉：

如果 n 个点中有的点大于 $y_{j}$，有的小于 $y_{j}$，那么拆出的绝对值就会分为两部分。

不妨设 $x_{i},i=1,2,\cdots,n$ 是按从小到大排序的，有 $k$ 个点 $x_{i},i=1,2,\cdots,k$ 比 $y_{j}$ 小，另外 $n-k$ 个点 $x_{i},i=k+1,\cdots,n$ 大于等于 $y_{j}$，那么 $q(j)$ 拆绝对值后的公式如下：

上式一共四项，后两项是前缀和后缀的累加和。也就是每次查询的时候都要求一次前后缀的累加和，这是前缀和解决的问题。

如果已经预处理了前缀和 $S(i) = \sum\limits_{j=1}\limits^{i}x_{j}$，那么 $q(j)$ 可以表示为：

对数组排序需要 $O(n\log n)$，$m$ 次查询每次需要 $O(\log n)$ 找到 $k$，因此总时间复杂度为 $O((m + n)\log n)$。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import bisect

class Solution:
    def minOperations(self, nums: List[int], queries: List[int]) -> List[int]:
        n = len(nums)
        nums.sort()
        sums = [0] * (n + 1)
        for i in range(1, n + 1):
            sums[i] = sums[i - 1] + nums[i - 1]
        m = len(queries)
        result = [-1] * m
        for j in range(m):
            y = queries[j]
            k = bisect.bisect(nums, y)
            result[j] = (k * 2 - n) * y + sums[n] - 2 * sums[k]
        return result
Share