leetcode第373題:検索と最小のK対数字(C++)

373.検索と最小のK対数値-力ボタン(LeetCode)
優先順位キューの典型的なテーマは、データ構造とアルゴリズムに似ています:44|最短パス:地図ソフトウェアはどのように最適な移動パスを計算しますか?zj-CSDNのブログの中の総括の引用部分、構想もLeetCodeの第743題と:ネットの遅延時間(C++)zj-CSDNブログのDijkstraアルゴリズムの優先度最適化の構想は似ている.
最も直接的には,可能なすべての要素ペアを優先キューに入れ,最後に前のk個を取り出す.しかし、このような脳が全部入っていると、メモリが爆発する可能性があります.
この問題の難点は,処理時にどのように重くするかであり,二重ポインタを用いて二つの配列間をスクロールすると重複項が現れる可能性がある(ハッシュテーブルでは重くするのは便利であるが,優先順位キューを用いるとコードが本当に肥大化しており,ハッシュテーブルはpairタイプを格納できないようである),二次元配列を使用しなくてもよいことではない.
しかし、2つの配列を2つのポインタでスクロールする必要はありません.参照:8 ms 100%、記録位置ポインタ高速解-探索と最小K対数値-力ボタン(LeetCode)

class Solution{
public:
    vector> kSmallestPairs(vector &nums1, vector &nums2, int k){
        int rows = nums1.size(), cols = nums2.size();
        vector> res; //    
        if (rows == 0 || cols == 0) return res;
        auto cmp = [&nums1, &nums2](const pair &a, const pair &b) { return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second]; };//      ，        nums1 nums2          
        priority_queue, vector>, decltype(cmp)> q(cmp);

        for (int i = 0; i < rows; i++)  q.emplace(i, 0);//     nums1   

        while (k > 0 && !q.empty()){
            k--; 
            auto cur = q.top();
            q.pop(); 
            //          ，        
            if (cur.second+1 <= cols-1){//      nums2   
                q.emplace(cur.first, cur.second + 1); //nums2         
            }

            res.push_back({nums1[cur.first], nums2[cur.second]});
        }
        return res;
    }
};

ああ、思考が硬直して、データ構造のそのブログの影響を受けてずっとその方向に考えて、思考が飛び出せなくて、ずっと繰り返しのことを考えて、自分を連れて行きました.
外に出て気持ちがさっぱりしていて、それから整理します.
最悪の方法では、すべての要素ペアを一度に優先順位キューに入れ、k回外に取ればいいです.欠点はメモリの消費量が大きいことです.
では、どのように最適化しますか?考えてみれば、配列要素の順序付けという条件は使用されていません.最小値を取り出すには、すべての要素をキューに入れる必要はありません.例を挙げると、nums 1の最初の要素とnums 2のすべての要素からなる要素のペアを優先順位キューに入れると、そのときのキューヘッダは必ず最小値になります.配列は昇順なので、キューヘッダを取り出して結果に入れることができます.
上の考え方は実は最初のコードが体現している考え方ですが、まだ効率的ではありません.私たちは実際にそんなに多くの要素をキューに入れる必要はありません.前のk個の最小の要素ペアを見つけるだけでいいので、kサイズのキューを維持すればいいです.
ここまで言ってみると、この考え方は前に何度も問題を使ったことがありますが、自分では思い出せませんでした.の

class Solution{
public:
    struct cmp{
        bool operator() (const pair &a, const pair &b) {
            return a.first + a.second < b.first + b.second; 
        }
    };
    vector> kSmallestPairs(vector &nums1, vector &nums2, int k){
        int n = nums1.size(), m = nums2.size();
        vector> res; //    
        if (n == 0 || m == 0) return res;
        priority_queue, vector>, cmp> q;//        

        for(int i = 0; i < n; ++i){//        
            for(int j = 0; j < m; ++j){
                if(q.size() < k)
                    q.push({nums1[i], nums2[j]});
                else if(nums1[i]+nums2[j] < q.top().first + q.top().second){//           ，      
                    q.pop();
                    q.push({nums1[i], nums2[j]});
                }
            }
        }
        while(!q.empty()){
            res.push_back({q.top().first, q.top().second});
            q.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};