50 DSA-Questions: Liste #38, #39

#38. Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked list is sorted in ascending order. Merge all the linked lists into one sorted linked list and return it.

class Solution {

    public ListNode mergeKLists(ListNode[] lists) {

        Queue<Integer> pq = new PriorityQueue<>();

        for (int k=0; k<lists.length; k++) {

            while (lists[k] != null) {

                pq.add(lists[k].val);

                lists[k] = lists[k].next;

            }

        }

        ListNode result = pq.isEmpty() ? null : new ListNode();

        ListNode node = result;

        while (!pq.isEmpty()) {

            node.val = pq.poll();

            node.next = pq.isEmpty() ? null : new ListNode();

            node = node.next;

        }

        return result;

    }

}

#39. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

class Node {

    int num;

    int valOcc; // number of occurrences

    Node (int num, int valOcc) {

        this.num = num;

        this.valOcc = valOcc;

    }

}

class Solution {

    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> occ = new HashMap<>();

        for (int num : nums) {

            if (!occ.containsKey(num)) {

                occ.put(num, 0);

            }

            occ.put(num, occ.get(num) + 1);

        }

        Set<Integer> keys = occ.keySet();

        Node[] nodes = new Node[keys.size()];

        int i = 0;

        for (Integer key : keys) {

            nodes[i++] = new Node(key, occ.get(key));

        }

        nodes = buildHeap(nodes);

        int [] result = new int[k];

        for (i=0; i<k; i++) {

            result[i] = nodes[0].num;

            nodes = heapify(removeMax(nodes), 0);

        }

        return result;

    }

    Node[] buildHeap(Node nodes[]) {

        // Index of last non-leaf node

        int start = ((nodes.length - 1) / 2) - 1;

 

        // Perform reverse level order traversal

        // from last non-leaf node and heapify

        // each node

        for (int i = start; i >= 0; i--) {

            nodes = heapify(nodes, i);

        }

        return nodes;

    }

    Node[] heapify(Node[] nodes, int i) {

        int indexMax = i; // current root

        int leftIndex = 2 * i + 1;

        int rightIndex = 2 * i + 2;

        if (leftIndex < nodes.length && nodes[leftIndex].valOcc > nodes[indexMax].valOcc) {

            indexMax = leftIndex;

        }

        if (rightIndex < nodes.length && nodes[rightIndex].valOcc > nodes[indexMax].valOcc) {

            indexMax = rightIndex;

        }

        if (indexMax != i) {

            Node aux = nodes[i]; // swap root with max

            nodes[i] = nodes[indexMax];

            nodes[indexMax] = aux;

            nodes = heapify(nodes, indexMax); // heapify the affected sub-tree

        }

        return nodes;

    }

    Node[] removeMax(Node[] nodes) {

        nodes[0] = nodes[nodes.length-1];

        Node [] copy = new Node[nodes.length - 1];

        System.arraycopy(nodes, 0, copy, 0, nodes.length - 1);

        return copy;

    }

}