arrays - 查找数组中唯一对的第 k 个最低和

Question

给定一组数字，每个数字代表一个问题的难度。排队的人应该选择任意两个问题来解决。两个选择的问题应该是不同的，这对问题不应该被任何人以前选择。因为他们知道困难，所以他们会选择困难总和最小的那对。
找出站在队列中第 k 个位置的人的最小难度总和。即来自数组的唯一对的第 k 个最小总和。
方法1:蛮力方法(O(n2))计算所有可能的唯一和并将其存储在数组中，并对唯一和数组进行排序以获得第k个元素。
方法 2:对困难数组进行排序并选择最小元素(对于前 4 个元素，我们可以有 6 个唯一对。因此，如果 k 小于或等于 6，我们可以使用排序数组中的前 4 个元素来找到最小总和)并用最小数组做了方法 1。
这 2 种方法没有解决超时情况。需要提高时间效率的解决方案。
注意:不同的问题也可以具有相同的难度级别(即数组可以包含重复的数字)，并且默认情况下不按排序顺序。

difficulties = [1,4,3,2,4]

Person comes first chooses: 1+2 = 3
2nd person: 1+3 = 4
3rd person: 1+4 (or) 1+4(since difficulty of two problems are 4) (or) 2+3 = 5
4th person: 2+3 (or) 1+4(based on the previous selection) = 5

所需的最终答案只是最小总和而不是实际元素。
假设约束为:
2 <= N <= 105
1 <= k <= N*(N-1)/2
1 <= 困难[i] <= 109
在哪里，
N 是数组的长度
k 是该人必须选择问题的位置

Answer 1

假设 k <= n*(n-1)/2 .如果没有，那么就不可能有答案。
我们可以使用二分查找来解决这个问题。我们对可能的对的总和进行二分搜索。
这里，低 = 可能的最小总和，即 low = difficulties[0] + difficulties[1] , 高 = 可能的最大总和，即 high = difficulties[n-1] + difficulties[n-2] .
所以，mid = low + (high - low)/2现在，在二分搜索的 1 次迭代中，我们将计算索引对 (i, j), i < j使得 difficulties[i] + difficulties[j] <= mid .如果计数小于 k，则 low = mid + 1否则如果计数 >= k，high = mid .现在，这一次迭代可以在 O(NlogN) 中完成。 .
你可以这样做直到(high - low) > 1 .因此，每次您将搜索空间减少一半。因此，总时间复杂度为 O(N*logN*logMaxsum)对于 N <= 1e6和 difficulties[i] <= 1e18将在不到 1 秒内运行。
现在高可以等于低或高可以等于低+1。答案可以等于low或 high .现在，您只需要解决问题是否为可能的总和(可以在 O(N) 中使用哈希轻松解决)，而否。指数对 (i, j), i < j使得 difficulties[i] + difficulties[j] <= low .如果这两个条件都满足，那么这就是您的答案。如果不是，那么答案就是高。
运行示例测试用例:
让我们考虑初始数组，difficulties = [1, 4, 3, 2, 4]和 k = 6 .
您首先对消耗我们的数组进行排序 O(NlogN) .排序后difficulties = [1, 2, 3, 4, 4]所有对n*(n-1)/2 = 10将是:

(1 + 2) => 3

(1 + 3) => 4

(1 + 4) => 5

(1 + 4) => 5

(2 + 3) => 5

(2 + 4) => 6

(2 + 4) => 6

(3 + 4) => 7

(3 + 4) => 7

(4 + 4) => 8

这更像是一个理解逻辑运行的伪代码。

sort(difficulties)
low = difficulties[0] + difficulties[1] // Minimum possible sum
high = difficulties[n-1] + difficulties[n-2] // Maximum possible sum

while(high - low > 1){
    mid = low + (high - low)/2
    count = all pairs (i, j) and i < j such that difficulties[i] + difficulties[j] <= mid.
    if(count < k){
        low = mid +1 
    }else{
        high = mid
    }
}

Iteration 1:
low = 3
high = 8
mid = 5
count = 5 [(1 + 2), (1 + 3), (1 + 4), (1 + 4), (2 + 3)]
count < k, so low = mid + 1 = 6

----------

Iteration 2:
low = 6
high = 8
mid = 7
count = 9 [(1 + 2), (1 + 3), (1 + 4), (1 + 4), (2 + 3), (2 + 4), (2 + 4), (3 + 4), (3 + 4)]
count >= k, so high= mid = 7

现在，while 循环停止，因为 high(7) - low(6) = 1。
现在，您需要检查总和 6 是否可能以及所有 (i, j) >= k 的计数。如果它那么低就是答案，在这种情况下它是真的。因此，对于 k = 6，答案 = 6。
要实现计数，您可以再次进行二分查找。选择第一个索引为 i那么你只需要找到 mid - difficulties[i]的上限在数组中 [i+1, n-1] .然后将 i 增加 1 并重复相同的操作。所以，你遍历每个索引 0 <= i <= n-1并在 [i+1, n-1]的数组搜索空间中找到它的上界并且每次迭代都需要 O(NlogN) .

要了解检查低或高是否为可能总和的最后一步，请尝试运行数组 difficulties = [10, 40, 30, 20, 40] 的算法。 .
更新:
下面是完整的工作代码，时间复杂度为 O(N*logN*logMaxsum)包括用于清楚理解逻辑的注释。

#include<bits/stdc++.h>
#define ll long long int

using namespace std;

void solve();
int main(){
    solve();
    return 0;
}

map<int, int> m;
vector<ll> difficulties;
ll countFunction(ll sum){
    /*
    Function to count all the pairs of indices (i, j) such that
    i < j and  (difficulties[i] + difficulties[j]) <= sum
    */
    ll count = 0;

    int n = (int)difficulties.size();
    for(int i=0;i<n-1;i++){
        /*
        Here the outer for loop means that if I choose difficulties[i]
        as the first element of the pair, then the remaining sum is
        m - difficulties[i], so we just need to find the upper_bound of this value
        to find the count of all pairs with sum <= m.
        upper_bound is an in-built function in C++ STL.
        */
        int x= upper_bound(difficulties.begin(), difficulties.end(), sum-difficulties[i]) - (difficulties.begin() + i + 1);
        if(x<=0){
            /*
            We break here because the condition of i < j is violated
            and it will be violated for remaining values of i as well.
            */
            break;
        }
        //cout<<"x = "<<x<<endl;
        count += x;
    }
    return count;
}


bool isPossible(ll sum){
    /*
    Hashing based solution to check if atleast 1 pair with
    a particular exists in the difficultiesay.
    */
    int n = (int) difficulties.size();
    for(int i=0;i<n;i++){
        /*
        Choosing the ith element as first element of pair
        and checking if there exists an element with value = sum - difficulties[i]
        */
        if(difficulties[i] == (sum - difficulties[i])){
            // If the elements are equal then the frequency must be > 1
            if(m[difficulties[i]] > 1){
                return true;
            }
        }else{
            if(m[sum - difficulties[i]] > 0){
                return true;
            }
        }
    }
    return false;
}

void solve(){
    ll i, j, n, k;
    cin>>n>>k;
    difficulties.resize(n);
    m.clear(); // to run multiple test-cases
    for(i=0;i<n;i++){
        cin>>difficulties[i];
        m[difficulties[i]]++;
    }
    sort(difficulties.begin(), difficulties.end());


    // Using binary search on the possible values of sum.
    ll low = difficulties[0] + difficulties[1]; // Lowest possible sum after sorting
    ll high = difficulties[n-1] + difficulties[n-2]; // Highest possible sum after sorting
    while((high-low)>1){
        ll mid = low + (high - low)/2;
        ll count = countFunction(mid);
        //cout<<"Low = "<<low<<" high = "<<high<<" mid = "<<mid<<" count = "<<count<<endl;
        if (k > count){
            low = mid + 1;
        }else{
            high = mid;
        }
    }

    /*
    Now the answer can be low or high and we need to check
    if low or high is a possible sum and does it satisfy the constraints of k.

    For low to be the answer, we need to count the number of pairs with sum <=low.
    If this count is >=k, then low is the answer.
    But we also need to check whether low is a feasible sum.
    */
    if(isPossible(low) && countFunction(low)>=k){
        cout<<low<<endl;
    }else{
        cout<<high<<endl;
    }
}