目标:
给定整数n
和k
,按字典顺序找到k
范围内第[1, ..,n]
个最小整数
示例:
输入:n=13,k=2
输出:10
说明:
词典的顺序是[1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]
,所以第二小的数字是10。你知道吗
我的代码适用于10^5以内的数字,但在10^6左右失败。我对用Python改进运行时一点都不熟悉。你知道吗
使用Python的排序方法不是一种方法吗?你知道吗
代码:
class Solution(object):
def findKthNumber(self, n, k):
"""
:type n: int
:type k: int
:rtype: int
"""
A = []
for i in range(1,n+1):
A.append(i)
x = (sorted(map(str, A)))
return int(x[k-1])
使用第k选择算法代替排序。你知道吗
修改代码。你知道吗
它将把最坏情况下的运行时间从O(n*logn)减少到O(n)。你知道吗
相关问题 更多 >
编程相关推荐