LeetCode1387.按幂值排序整数将整数字权力重排序【Medium】【Python】【排序】问题LeetCode一个整数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]内的所有整数按幂值升序排序，如果两个或多个整数的幂值相同则按升序排序。返回范围[lo中的第k个整数,hi]按幂值排序。请注意，对于任何整数x(lo<=x<=hi)，可以保证使用这些步骤将x转换为1，并且x的幂是32位有符号整数.Example1:Input:lo=12,hi=15,k=2Output:13Explanation: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=1，hi=1，k=1输出：1示例3：输入：lo=7，hi=11，k=4输出：7说明：幂数组对应于区间[7,8,9,10,11]是[16,3,19,6,14]。按幂排序的区间是[8,10,11,7,9]。排序数组中的第四个数字是7。示例4：输入：lo=10，hi=20，k=5输出：13示例5：输入：lo=1,hi=1000,k=777Output:570Constraints:1<=lo<=hi<=10001<=k<=hi-lo+1问题我们将整数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]中的整数进行升序排序。如果大于或等于2个整数具有相同的权重，则根据数字本身的值将它们升序排序。请返回区间[lo,hi]中按权重排序的第k个整数。注意题目保证对于任意整数x(lo<=x<=hi)，变为1所需要的步数是一个32位有符号整数。示例1：输入：lo=12,hi=15,k=2输出：13解释：12的权重为9(12-->6-->3-->10-->5-->16-->8-->4-->2-->1）13的权重为914，1715的权重为17，区间内的数字按权重排序，结果为[12,13,14,15]。对于k=2，答案是第二个整数13。注意12和13的权重是一样的，所以我们自己按升序排序。14和15是一样的。示例2：输入：lo=1,hi=1,k=1输出：1示例3：输入：lo=7,hi=11,k=4输出：7解释：区间[7,8,9中的整数,10,11]对应带权重的[16,3,19,6,14]。按重量排序得到[8,10,11,7,9]。排序数组中的第4个数字是7。示例4：输入：lo=10,hi=20,k=5输出：13示例5：输入：lo=1,hi=1000,k=777输出：570提示：1<=lo<=hi<=10001<=k<=hi-lo+1排序思路将values和weights构造成字典，然后先value再key排序。Python3代码类解决方案：defgetKth(self,lo:int,hi:int,k:int)->int:nums,weight=[],[]forxinrange(lo,hi+1):nums.append(x)weight.append(self.step(x))#将两个列表合并成一个字典dic=dict(zip(nums,weight))#先按权重排序，再按值排序res=sorted(dic.items(),key=lambdax:(x[1],x[0]))returnres[k-1][0]defstep(self,x):cnt=0ifx==1:returncntwhilex!=1:ifx%2:x=3*x+1else:x=x/2cnt+=1returncntGitHublinkPython
