数组元素和一组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

1

1

时间限制：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，它与其他elemets的k最小距离将是与数组中k中围绕它的距离。（当然，它可能是在右边或左边，或者从两边）。

因此，对于每个要计算的元素，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

我们可以通过采用滑动窗口方法来有效地解决这个问题。

假设数组中没有重复项似乎是安全的。如果它包含重复项，那么我们可以在< code>HashSet的帮助下简单地丢弃它们。

下一步是对数组进行排序，以保证最近的k个元素将在窗口< code >[I-k；i k]对于每个索引I

我们将为窗口保留三个变量：左，右和当前和当前Sum。它们将在每次迭代时进行相应的调整。最初，left = 0 和 right = k（因为索引 0 处的元素左侧没有元素），而 currentSum = 索引 0 的结果。

为了重新计算 currentSum，我建议写下两个相邻迭代的表达式，并仔细研究它们之间的差异。
例如，如果 result[i] = nums[i 1] ... nums[i right] - （nums[i - 1] ... nums[i - left]） （left - right） * nums[i]， then
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进行了排序并计算了映射元素-

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

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