leetcode 1387. Sort Integers by The Power Value （python）

「 This is my participation 11 The fourth of the yuegengwen challenge 16 God , Check out the activity details ：2021 One last more challenge 」

describe

The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps:

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

For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1).

Given three integers l_o, h_i and k. The task is to sort all integers in the interval [l_o, h_i] by the power value in ascending order, if two or more integers have the same power value sort them by ascending order.

Return the k-th integer in the range [l_o, h_i] sorted by the power value.

Notice that for any integer x (l_o <= x <= h_i) it is guaranteed that x will transform into 1 using these steps and that the power of x is will fit in 32 bit signed integer.

Example 1:

Input: lo = 12, hi = 15, k = 2
Output: 13
Explanation: The power of 12 is 9 (12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)
The power of 13 is 9
The power of 14 is 17
The power of 15 is 17
The interval sorted by the power value [12,13,14,15]. For k = 2 answer is the second element which is 13.
Notice that 12 and 13 have the same power value and we sorted them in ascending order. Same for 14 and 15.
 Copy code 

Example 2:

Input: lo = 1, hi = 1, k = 1
Output: 1
 Copy code 

Example 3:

Input: lo = 7, hi = 11, k = 4
Output: 7
Explanation: The power array corresponding to the interval [7, 8, 9, 10, 11] is [16, 3, 19, 6, 14].
The interval sorted by power is [8, 10, 11, 7, 9].
The fourth number in the sorted array is 7.
 Copy code 

Example 4:

Input: lo = 10, hi = 20, k = 5
Output: 13
 Copy code 

Example 5:

Input: lo = 1, hi = 1000, k = 777
Output: 570
 Copy code 

Note:

1 <= lo <= hi <= 1000
1 <= k <= hi - lo + 1
 Copy code 

analysis

According to the meaning , Is to give a calculation of a number power Methods , That is to put a number x Turn into 1 The number of times to go through the following operations ：

• x If it's even, then x/=2
• x If it's odd, then x = 3*x+1

Then the range is given [lo, hi] and k , Ask us to rank the interval in ascending power order [lo, hi] Sort all integers in , If two or more integers have the same power value , Sort them in ascending order . Returns the values sorted by power [lo, hi] Within the scope of k It's an integer . The title ensures that all certificates can be obtained from x Turn into 1 .

The simplest way is to follow the meaning of the question , Write a to get a number power The value of the function getPower . Then all integers are sorted by power Value permutation , Finally, return to No k It's just an integer .

answer

class Solution(object):
    def getKth(self, lo, hi, k):
        """
        :type lo: int
        :type hi: int
        :type k: int
        :rtype: int
        """
        def getPower(n):
            result = 0
            while n!=1:
                if n%2==0:
                    n = n//2
                else:
                    n = n * 3 + 1
                result += 1
            return result
        d = []
        for i in range(lo,hi+1):
            d.append([i,getPower(i)])
        d = sorted(d, key=lambda x: x[1])
        return d[k-1][0]
            
        	      
		
 Copy code 

Running results

Runtime: 708 ms, faster than 35.66% of Python online submissions for Sort Integers by The Power Value.
Memory Usage: 13.6 MB, less than 86.82% of Python online submissions for Sort Integers by The Power Value.
 Copy code 

analysis

The above solution is from [lo, hi] There are many pairs of numbers in the process of calculating one by one power The process of value is repeated , You can use a dictionary d Direct records already know power The number of , In this way, a lot of calculation time can be saved in the later calculation process .

answer

class Solution(object):
    def getKth(self, lo, hi, k):
        """
        :type lo: int
        :type hi: int
        :type k: int
        :rtype: int
        """
        d = {1: 1}
        def getPower(n):
            if n not in d:
                if n % 2 == 0:
                    d[n] = 1 + getPower(n / 2)
                else:
                    d[n] = 1 + getPower(3*n + 1)
            return d[n]
        return sorted((getPower(i), i) for i in range(lo, hi+1))[k-1][1]
            
 Copy code 

Running results

Runtime: 164 ms, faster than 95.35% of Python online submissions for Sort Integers by The Power Value.
Memory Usage: 42.7 MB, less than 11.63% of Python online submissions for Sort Integers by The Power Value.
 Copy code 

Original link ：leetcode.com/problems/so…

Your support is my greatest motivation