Why I got Time Limit Exceeded with C++


  • 0
    L

    I use the idea of heap, though it is not a total heap, I just put the max element on the top of the heap, every time I just compare the max element of the heap with the next coming value in the matrix, if the value is smaller than the max element , just replace it and build new heap.
    Here is my code, I want to figure how it can be improved to be faster.

    class Solution {
    public:
        int kthSmallest(vector<vector<int>>& matrix, int k) {
            vector<int> heap(k,0);
            int i = 0;
            for (auto row: matrix) {
                if (i == k && row[0] > heap[0]) break;
                for (auto elem: row) {
                    if (i < k) {
                        heap[i] = elem;
                        ++i;
                        if (i == k) buildHeap(heap, k);
                        continue;
                    }
                    if (elem > heap[0]) break;
                    else {
                        heap[0] = elem;
                        buildHeap(heap, k);
                    }
                }
            }
            return heap[0];
        }
        
        void percDown(vector<int>& heap, int i, int len) {
            int tmp;
            int child = 2*i+1;
            if ( child + 1 < len && heap[child] < heap[child+1]) ++child;
            if (heap[i] < heap[child]) {
                tmp = heap[i];
                heap[i] = heap[child];
                heap[child] = tmp;
            }
        }
        void buildHeap(vector<int>& heap, int len) {
            for (int i = (len-1)/2; i >= 0; --i) percDown(heap, i, len);
        }
    };
    

    Thanks.


  • 0

    Try priority_queue in C++


Log in to reply
 

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