current position：Home>leetcode 1387. Sort Integers by The Power Value （python）
leetcode 1387. Sort Integers by The Power Value （python）
20220131 15:54:48 【Wang Daya】
「 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 kth 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[k1][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))[k1][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
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201311554469020.html
The sidebar is recommended
 Django (make an epidemic data report)
 Daily python, Part 8  if statement
 Django model class 1
 The same Python code draws many different cherry trees. Which one do you like?
 Python code reading (Chapter 54): Fibonacci sequence
 Django model class 2
 Python crawler Basics
 Mapping 3D model surface distances using Python VTK
 How to implement encrypted message signature and verification in Python  HMAC
 leetcode 1945. Sum of Digits of String After Convert（python）
guess what you like

leetcode 2062. Count Vowel Substrings of a String（python）

Analysis of Matplotlib module of Python visualization

Django permission management

Python integrated programming  visual hot search list and new epidemic situation map

[Python data collection] scripy realizes picture download

Python interface automation test framework (basic part)  loop statement of process control for & while

Daily python, Chapter 9, while loop

Van * Python  save the crawled data with docx and PDF

Five life saving Python tips

Django frequency control
Random recommended
 Python  convert Matplotlib image to numpy Array or PIL Image
 Python and Java crawl personal blog information and export it to excel
 Using class decorators in Python
 Untested Python code is not far from crashing
 Python efficient derivation (8)
 Python requests Library
 leetcode 2047. Number of Valid Words in a Sentence（python）
 leetcode 2027. Minimum Moves to Convert String（python）
 How IOS developers learn Python Programming 5  data types 2
 leetcode 1971. Find if Path Exists in Graph（python）
 leetcode 1984. Minimum Difference Between Highest and Lowest of K Scores（python）
 Python interface automation test framework (basic)  basic syntax
 Detailed explanation of Python derivation
 Python reptile lesson 29 Chinese monster database. It is found that there is a classification of color (he) desire (Xie) monsters during operation
 A brief note on the method of creating Python virtual environment in Intranet Environment
 [worth collecting] for Python beginners, sort out the common errors of beginners + Python Mini applet! (code attached)
 [Python souvenir book] two people in one room have three meals and four seasons: 'how many years is it only XX years away from a hundred years of good marriage' ~?? Just come in and have a look.
 The unknown side of Python functions
 Python based interface automation test project, complete actual project, with source code sharing
 A python artifact handles automatic chart color matching
 Python crawls the map of Gaode and the weather conditions of each city
 leetcode 1275. Find Winner on a Tic Tac Toe Game（python）
 leetcode 2016. Maximum Difference Between Increasing Elements（python）
 Run through Python date and time processing (Part 2)
 Application of urllib package in Python
 Django API Version (II)
 Python utility module playsound
 Database addition, deletion, modification and query of Python Sqlalchemy basic operation
 Tiobe November programming language ranking: Python surpasses C language to become the first! PHP is about to fall out of the top ten?
 Learn how to use opencv and python to realize face recognition!
 Using OpenCV and python to identify credit card numbers
 Principle of Python Apriori algorithm (11)
 Python AI steals your voice in 5 seconds
 A glance at Python's file processing (Part 1)
 Python cloud cat
 Python crawler actual combat, pyecharts module, python data analysis tells you which goods are popular on free fish~
 Using pandas to implement SQL group_ concat
 How IOS developers learn Python Programming 8  set type 3
 windows10+apache2. 4 + Django deployment
 Django parser