거듭제곱 값으로 정수 정렬

정수x의 거듭제곱은 다음 단계를 사용하여 x를 1로 변환하는 데 필요한 단계 수로 정의됩니다.

x가 짝수이면 x = x / 2

x가 홀수이면 x = 3 * x + 1

예를 들어, x = 3가 7 ( 3 )가 되기 위해서는 7 단계가 필요하기 때문에 1의 거듭제곱은 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1입니다.
lo , hi 및 k 세 개의 정수가 주어집니다. 작업은 간격[lo, hi]의 모든 정수를 거듭제곱 값으로 오름차순으로 정렬하는 것입니다. 두 개 이상의 정수가 동일한 거듭제곱 값을 갖는 경우 오름차순으로 정렬합니다.

검정력 값으로 정렬된 kth 범위의 [lo, hi] 정수를 반환합니다.

모든 정수 x (lo <= x <= hi)에 대해 이러한 단계를 사용하여 x가 1로 변환되고 x의 거듭제곱이 32비트 부호 있는 정수에 맞도록 보장됩니다.

예 1:

입력: lo = 12, hi = 15, k = 2
출력: 13
설명: 12의 거듭제곱은 9입니다(12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1).
13의 거듭제곱은 9
14의 거듭제곱은 17
15의 거듭제곱은 17
검정력 값 [12,13,14,15]로 정렬된 간격입니다. k = 2인 경우 답은 두 번째 요소인 13입니다.
12와 13은 동일한 거듭제곱 값을 가지며 오름차순으로 정렬했습니다. 14와 15도 마찬가지입니다.

예 2:

입력: lo = 7, hi = 11, k = 4
출력: 7
설명: 간격 [7, 8, 9, 10, 11]에 해당하는 전력 배열은 [16, 3, 19, 6, 14]입니다.
거듭제곱으로 정렬된 간격은 [8, 10, 11, 7, 9]입니다.
정렬된 배열의 네 번째 숫자는 7입니다.

제약:

1 <= lo <= hi <= 1000

1 <= k <= hi - lo + 1

해결책:

import heapq

class Solution:
    def getPower(self, n):
        if n == 1:
            return 0
        if n in self.power:
            return self.power[n]
        if n & 1:
            val = 1 + self.getPower(3 * n + 1)
        else:
            val = 1 + self.getPower(n >> 1)
        self.power[n] = val
        return val


    def getKth(self, lo: int, hi: int, k: int) -> int:
        self.power = {}
        heap = []
        for num in range(lo, hi + 1):
            heapq.heappush(heap, (-self.getPower(num), -num))
            if len(heap) > k:
                heapq.heappop(heap)
        return -heap[0][1]