My c++ solution, use loser tree, 40ms


  • 0
    P

    Maybe It's not concise enough. I just want to try loser tree.

    class Solution {
    int k;
    int minVal = 1 << 31;
    int maxVal = (int)((unsigned int)1 << 31 - 1);
    

    public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
    if (lists.empty())
    return NULL;

        k = lists.size();    
        if (k == 1)
            return lists[0];
    
        vector<int> lose;
        vector<int> data;
        lose.resize(k);
        data.resize(k + 1);
        data[k] = minVal;
    
        int i, s;
        for (i = 0; i < k; i++) {
            lose[i] = k;
            data[i] = lists[i] ? lists[i]->val : maxVal;
        }
    
        for (i = k - 1; i >= 0; i--) {
            adjust(i, data, lose);
        }
    
        ListNode first(0);
        ListNode *node = &first;
    
        while (data[lose[0]] != maxVal) {
            node->next = lists[lose[0]];
            node = node->next;
            lists[lose[0]] = node->next;
            data[lose[0]] = lists[lose[0]] ? lists[lose[0]]->val : maxVal;
            adjust(lose[0], data, lose);
        }
    
        return first.next;
    }
    
    void adjust(int id, vector<int> &data, vector<int> &lose) {
        int s, tmp;
        for (s = (id + k) / 2; s > 0; s = s / 2) {
            if (data[id] > data[lose[s]]) {
                tmp = lose[s];
                lose[s] = id;
                id = tmp;
            }
        }
    
        lose[0] = id;
    }
    

    };


Log in to reply
 

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