Skip to main content

Command Palette

Search for a command to run...

PriorityQueue - LC

Published
•1 min read•View as Markdown
PriorityQueue  - LC

#1 https://leetcode.com/problems/sort-integers-by-the-power-value/

    class Solution {
         int help(int x) {
            if (x == 1) {
                return 1;
            }
            int total = 0;
            while (x != 1) {
                if (x % 2 == 0) {
                x = x / 2;
                ++total;
                } else {
                x = 3 * x + 1;
                ++total;
                }
            }
            return total;
        }
        public int getKth(int lo, int hi, int k) {
            PriorityQueue<int[]> queue = new PriorityQueue<>(
                (a, b) -> a[1] == b[1] ? a[0] - b[0] : a[1] - b[1]);

            for (int i = lo; i <= hi; i++) {
                int[] arr = new int[]{i, help(i)};
                queue.add(arr);
            }
            while (k > 1) {
                queue.poll();
                --k;
            }

            return queue.peek()[0];
        }        

#2 https://leetcode.com/problems/queue-reconstruction-by-height/submissions/

       class Solution {
            public int[][] reconstructQueue(int[][] people) {
             if (people == null || people.length == 0 || 
                  people[0].length == 0)
                return new int[0][0];

               PriorityQueue<int[]> queue = new PriorityQueue<>(
               (a,b) -> a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]);

               for(int[] curr : people) {
                        queue.add(curr);
               }

               List<int[]> result = new ArrayList<>();
               while(!queue.isEmpty()) {
                         int[] person = queue.poll();
                         result.add(person[1], person);    
               }

               return result.toArray(new int[people.length][2]);
            }
        }