5350. 将整数按权重排序

5350. 将整数按权重排序

topK的问题，可以考虑用堆来维护，比如说这个题，维护一个大小为k的最大堆（当然最大是自定义排序后的最大），那么在堆中的元素就是从小到大的元素。因为是大根堆，堆顶元素就是堆中的topK；

元素入堆时：

• 如果元素入堆时，加入元素比堆顶小，就更换堆顶元素；
• 否则无操作

通过维护一个堆（java中用优先队列实现），那么堆顶元素就是我们要的topK了。

优化：

另外就本题来说，每一个数的权值都是一定的，如果之前算过了，就直接从map中获得

class Solution {
    public int getKth(int lo, int hi, int k) {
    	//大根堆
    	PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)-> {
    		if(o1[1] == o2[1]) {	//如果权重相同,按数字本身大小排序
    			return o2[0] - o1[0];	
    		}
    		return o2[1] - o1[1];
    	});
    	HashMap<Integer, Integer> hs = new HashMap<>();
    	for (int i = lo; i <= hi; i++) {
			int temp = i;
			int count = 0;
			while(temp != 1) {
				if(hs.containsKey(temp)) {	//如果算过，用缓存中的权值
					count = hs.get(temp) + count;
					break;
				}else {
					if(temp%2 == 0) {
						temp >>= 1;
					}else {
						temp = 3*temp +1;
					}
					count++;
				}
			}
			if(!hs.containsKey(i)) {	//算完了，就放入缓存
				hs.put(i, count);
			}
			int[] arr = new int[2];
			arr[0] = i;
			arr[1] = count;
			if(pq.size() < k) {	//维护一个大小为k的最大堆
				pq.offer(arr);
			}else {
				int[] top = pq.peek();
				if(arr[1] < top[1] || (arr[1] == top[1] && arr[0] < top[0])) {
					pq.poll();
					pq.offer(arr);
				}
			}
		}
    	return pq.poll()[0];
    }
}