C++ Solution with Heap Sort implemented


  • 0
    T
    class Solution {
    public:
        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            if (nums1.empty() || nums2.empty()) return vector<pair<int, int>>();
            vector<pair<int, int>> bucket;
            vector<pair<int, int>> result;
            for (int i=0; i < nums1.size(); i++){
                for (int j=0; j < nums2.size(); j++){
                    bucket.push_back(make_pair(nums1[i], nums2[j]));
                }
            }
            
            if (k > bucket.size()) k = bucket.size(); 
            get_kth_element_sorted(bucket, k);
            for (int i=0; i < k; i++) {
                result.push_back(bucket[bucket.size()-1-i]);
            }
            return result;
        }
        
        int left(int idx){
            return (idx << 1) + 1;
        }
        int right(int idx){
            return (idx << 1) + 2;
        }
        //
        void min_heapify(vector<pair<int, int>>& bucket, int idx){
            int l = left(idx);
            int r = right(idx);
            int smallest = idx;
            if (l < heap_size && (bucket[l].first+bucket[l].second) < (bucket[smallest].first+bucket[smallest].second)) smallest = l;
            if (r < heap_size && (bucket[r].first+bucket[r].second) < (bucket[smallest].first+bucket[smallest].second)) smallest = r;
            if (smallest !=idx){
                swap(bucket[smallest], bucket[idx]);
                min_heapify(bucket, smallest);
            }
        }
        //construct heap
        void construct_min_heap(vector<pair<int, int>>& bucket){
            heap_size = bucket.size();
            for (int i=(heap_size << 1)-1; i >=0; i--){
                min_heapify(bucket, i);
            }
        }
        
        void get_kth_element_sorted(vector<pair<int, int>>& bucket, int k){
            construct_min_heap(bucket);
            for (int i=0; i < k; i++) {
                swap(bucket[heap_size-1], bucket[0]);
                heap_size--;
                min_heapify(bucket, 0);
            }
        }
        private:
            int heap_size;
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.