# 1387. Sort Integers by The Power Value
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/sort-integers-by-the-power-value/
## 思路
先用dp算出每个数字的power value然后排序
## Code
java

class Solution {
    public int getKth(int lo, int hi, int k) {
        Map<Integer, Integer> dp = new HashMap<>();
        dp.put(1, 0);
        List<int[]> list = new ArrayList<>();
        for(int i=lo; i<=hi; i++){
            list.add(new int[]{i, getPowerValue(i, dp)});
        }
        Collections.sort(list, (a,b)->(a[1]==b[1]?a[0]-b[0]:a[1]-b[1]));
        return list.get(k-1)[0];
    }
    private int getPowerValue(int num, Map<Integer, Integer> dp){
        if(dp.containsKey(num)) return dp.get(num);
        if(num%2==0) dp.put(num, getPowerValue(num/2, dp)+1);
        else dp.put(num, getPowerValue(num*3+1, dp)+1);
        return dp.get(num);
    }
}

c++

class Solution {
public:
    int getKth(int lo, int hi, int k) {
        map<int, int> map;
        map.insert({1,0});
        vector<pair<int, int>> sorted;
        for(int i=lo; i<=hi; i++){
            int p = powerValue(map, i);
            sorted.push_back({p, i});
        }
        sort(sorted.begin(), sorted.end());
        return sorted[k-1].second;
    }
    int powerValue(map<int, int>& map, int num){
        int ans = 0;
        if(map.find(num)!=map.end()) return map[num];
        if(num%2==0) ans = powerValue(map, num/2)+1;
        else ans = powerValue(map, num*3+1)+1;
        map.insert({num, ans});
        return ans;
    }
};