1387. Sort Integers by The Power Value

Memo + Sort

TC: O(nlogn + kn), k is getPower TC

S: O(n)

class Solution {
    Map<Integer, Integer> memo = new HashMap<>(); //use common Map to save, same number's count
    
    public int getKth(int lo, int hi, int k) {
        int[][] result = new int[hi-lo+1][];
        for (int i = lo; i <= hi; i++) {
            result[i-lo] = new int[]{i, getPower(i)};
        }
        Arrays.sort(result, (a, b) -> a[1] - b[1]);
        return result[k-1][0];
    }
    
    private int getPower(int x) {
        if (x == 1) { // base case
            return 0;
        }
        if (memo.containsKey(x)) {
            return memo.get(x);
        }
        
        memo.put(x, (x % 2 == 0) ? getPower(x/2)+1 : getPower(3*x + 1)+1);
        return memo.get(x);
    }
}

/*
ex lo = 12, hi = 18

12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1

so 16 will cal again in the future (larger than frist one: 12)
so use a common map to memo

at last sort result
O(nk+ nlogn), k is the getPower's TC

a better one is using PQ ()

*/

Memo + PQ

O(nx+ nlogk)

class Solution {
    Map<Integer, Integer> memo = new HashMap<>(); //use common Map to save, same number's count
    
    public int getKth(int lo, int hi, int k) {
        // count same: poll larger index, or poll larger count
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[1] == b[1]) ? b[0] - a[0] : b[1] - a[1]); 
        for (int i = lo; i <= hi; i++) {
            pq.offer(new int[]{i, getPower(i)});
            if (pq.size() > k) {
                pq.poll();
            }
        }
        return pq.poll()[0];
    }
    
    private int getPower(int x) {
        if (x == 1) { // base case
            return 0;
        }
        if (memo.containsKey(x)) {
            return memo.get(x);
        }
        
        memo.put(x, (x % 2 == 0) ? getPower(x/2)+1 : getPower(3*x + 1)+1);
        return memo.get(x);
    }
}

/*
ex lo = 12, hi = 18

12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1

so 16 will cal again in the future (larger than frist one: 12)
so use a common map to memo

at last sort result
O(nx+ nlogn), x is the getPower's TC

a better one is using PQ 
O(nx+ nlogk)

*/