Sort Integers by The Power Value

给一个数字n, 按照以下处理后, 求结果第k个大的数字是什么.

• if x is even then x = x / 2
• if x is odd then x = 3 * x + 1

肯定要算下的, 用memo算下, 然后建个map存下, 然后排序, 然后找第k个.

class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    class Pair{
        int a;
        int b;
        Pair(int a, int b){
            this.a = a;
            this.b = b;
        }
    }
    public int getKth(int lo, int hi, int k) {
        List<Pair> list = new ArrayList<>(); 
        for(int i = lo; i <= hi; i++)
            list.add(new Pair(power(i), i));
        Collections.sort(list, (a, b) -> {
            if(a.a == b.a)
                return a.b - b.b;
            else
                return a.a - b.a;
        });
        k--;
        return list.get(k).b;
    }
    public int power(int n){
        if(n == 1)
            return 0;
        if(map.containsKey(n))
            return map.get(n);
        if(n % 2 == 0){
            map.put(n, 1 + power(n / 2));
        }
        else{
            map.put(n, 1 + power(3 * n + 1));
        }
        return map.get(n);
    }
}