数组元素与 k 个数组元素的集合之间的距离的最小总和（绝对差）

Question

我需要找到数组中的元素与数组的 k 个元素集之间的距离的最小总和，不包括该索引。

例如：

arr = {5, 7, 4, 9}

k = 2

min_sum(5) = |5-4| + |5-7| = 3

min_sum(7) = |7-9| + |7-5| = 4

min_sum(4) = |4-5| + |4-7| = 4

min_sum(9) = |9-7| + |9-5| = 6

因此，一个天真的解决方案是从数组的每个元素中减去第 i 个元素，然后对数组进行排序并计算排序数组中前 k 个元素的总和。但这需要太长时间...我相信这是一个 dp 问题或类似的问题（也许是 treaps）。

输入：

n - 数组元素的数量

k - 集合中的元素数

数组

限制条件：

2 <= n <= 350 000

1 <= k < n

1 <= a[i] <= 10^9

时限：2秒

输入：

4

2

5 7 4 9

输出：

3 4 4 6

解决这个问题最有效的方法是什么？如何优化搜索最小和？

这是我用 C++ 编写的代码，对于 n = 350 000、k = 150 000，它工作了大约 3 分钟：

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n, k, tp;
    unsigned long long temp;
    cin >> n >> k;

    vector<unsigned int> org;
    vector<unsigned int> a;
    vector<unsigned long long> cum(n, 0);
    //unordered_map <int, long long> ans;
    unordered_map <int, long long> mp;


    for (int i = 0; i < n; i++){
        cin >> tp;
        org.push_back(tp);
        a.push_back(tp);
    }

/*
    srand(time(0));

    for (int i = 0; i < n; i++){
        org.push_back(rand());
        a.push_back(org[i]);
    }
*/

    sort(a.begin(), a.end());
    partial_sum(a.begin(), a.end(), cum.begin());

    mp[a[0]] = cum[k] - cum[0] - a[0] * k;
    //ans[a[0]] = mp[a[0]];

    for (int i = 1; i <= k; i++) {
       mp[a[i]] = a[i] * i - cum[i-1] + cum[k] - cum[i] - a[i] * (k-i);
    }

    for (int i = 1; i < n-k; i++){
        for (int j = 0; j <= k; j++){
            //if (ans.find(a[i+j]) != ans.end()) {continue;}
            temp = ( (a[i+j] * j) - (cum[i+j-1] - cum[i-1]) ) + ( cum[i+k] - cum[i+j] - a[i+j] * (k-j) );
            if (mp.find(a[i+j]) == mp.end()) { mp[a[i+j]] = temp; }
            else if (mp[a[i+j]] > temp) { mp[a[i+j]] = temp; }
            //else { ans[a[i+j]] = mp[a[i+j]]; }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << mp[org[i]] << " ";
    }

    return 0;
}

Answer 1

我觉得这个比较好：

首先对数组进行排序，然后你就可以知道事实 - 对于数组中的每个元素 i，它与其他元素的 k 最小距离将是与数组中 k 中放置在它周围的元素的距离。（当然可能是向右或向左或两侧）。

所以对于每个元素 i 要计算 min_sum(a[i]) 这样做：

首先，min_sum(a[i]) = 0.

然后，使用两个索引，让我们将它们标记为 r（在 i 的右侧）和 l（在 i 的左侧）并将距离 (a[i]-a[r]) 与距离 (a[i]-a[l]) 进行比较。您将最小的添加到 min_sum(a[i]) 并且如果它是正确的那么增加索引 r，如果它是左边的，则减少索引 l。当然，如果左侧变为 0 或右侧变为 n，您将最接近另一侧的元素。不管怎样，你这样做直到你对 k 个元素求和，就是这样。

这样你就不会对主数组以外的任何东西进行排序。

Answer 2

我们可以通过滑动 window 方法有效地解决这个问题。

可以安全地假设数组中没有重复项。如果它包含重复项，那么我们可以在 HashSet.

的帮助下简单地丢弃它们

下一步是对数组进行排序，以保证对于每个索引 i.

，最接近的 k 个元素将在 window [i - k; i + k] 内

我们将为 window 保留三个变量：left、right 和 currentSum。它们将在每次迭代中相应地进行调整。最初，left = 0 和 right = k（因为索引 0 处的元素左侧没有元素）和索引 0 的 currentSum = result。

关键考虑因素是变量 left 和 right 在迭代过程中不太可能改变 'significantly'。更准确地说，在每次迭代中，我们应该尝试通过比较距离 nums[i + right + 1] - nums[i] 与 nums[i] - nums[i - left] 来将 window 向右移动。（你可以从数学上证明，试图将 window 向左移动是没有意义的。）如果前者小于后者，我们在更新 currentSum 的同时向右递增和向左递减。

为了重新计算 currentSum，我建议写下两个相邻迭代的表达式并仔细查看它们之间的差异。
例如，如果 result[i] = nums[i + 1] + ... + nums[i + right] - (nums[i - 1] + ... + nums[i - left]) + (left - right) * nums[i], 然后
result[i] = nums[i + 2] + ... + nums[i + right] - (nums[i] + ... + nums[i - left]) + (left - right + 2) * nums[i + 1].
正如我们所看到的，这些表达式非常相似。该解的时间复杂度为O(n * log(n))。（我在 Java 中针对 n ~ 500_000 和 k ~ 400_000 的解决方案在 300 毫秒内有效）我希望这与上面的考虑对您有所帮助。

假设我们已经对原始数组 nums 进行了排序并计算了映射 element->its index in the sorted array（例如，通过二进制搜索），我们可以继续查找距离。

public long[] findMinDistances(int[] nums, int k) {
    long[] result = new long[nums.length];
    long currentSum = 0;
    for (int i = 1; i <= k; i++) {
        currentSum += nums[i];
    }
    result[0] = currentSum - (long) k * nums[0];

    int left = 0;
    int right = k;
    currentSum = result[0];
    for (int i = 1; i < nums.length; i++) {
        int current = nums[i];
        int previous = nums[i - 1];
        currentSum -= (long) (left - right) * previous;
        currentSum -= previous;

        if (right >= 1) {
            currentSum -= current;
            left++;
            right--;
        } else {
            currentSum += nums[i - 1 - left];
        }
        currentSum += (long) (left - right) * current;

        while (i + right + 1 < nums.length && i - left >= 0 &&
                nums[i + right + 1] - current < current - nums[i - left]) {
            currentSum += nums[i + right + 1] - current;
            currentSum -= current - nums[i - left];
            right++;
            left--;
        }
        result[i] = currentSum;
    }
    return result;
}

对于原始数组中的每个元素 e，其最小距离总和将为 result[mapping.get(e)]。

数组元素与 k 个数组元素的集合之间的距离的最小总和（绝对差）

Min sum of distances (absolute differences) between array element and set of k array elements

c++

arrays

algorithm

heap

dynamic-programming