现有n个正整数,0 < n ≤ 1000,要求出这n个正整数中的第k个最小整数(相同大小的整数只计算一次),0 < k ≤ 100,正整数均不大于30000。 输入 第一行为n和k; 第二行开始为n个正整数的值,整数间用空格隔开。 输出 第k个最小整数的值;若无解,则输出“NO RESULT”
时间: 2023-05-13 14:06:25 浏览: 52
这是一个典型的选择算法问题,可以使用快速选择算法来解决。具体步骤如下:
1. 读入n和k,以及n个正整数的值。
2. 对这n个正整数进行快速选择算法,找到第k个最小整数。
3. 如果找到了第k个最小整数,则输出它的值;否则输出“NO RESULT”。
以下是快速选择算法的伪代码:
function quick_select(A, k):
if A is empty:
return NO RESULT
else:
pivot = choose_pivot(A)
left = [x for x in A if x < pivot]
right = [x for x in A if x > pivot]
equal = [x for x in A if x == pivot]
if k <= len(left):
return quick_select(left, k)
elif k <= len(left) + len(equal):
return pivot
else:
return quick_select(right, k - len(left) - len(equal))
其中,choose_pivot是选择主元的函数,可以使用随机选择或者中位数选择等方法。在本题中,由于数据范围较小,可以直接选择中位数作为主元。
以下是完整的Python代码实现:
n, k = map(int, input().split())
nums = list(map(int, input().split()))
def quick_select(A, k):
if not A:
return "NO RESULT"
else:
pivot = sorted(A)[len(A)//2]
left = [x for x in A if x < pivot]
right = [x for x in A if x > pivot]
equal = [x for x in A if x == pivot]
if k <= len(left):
return quick_select(left, k)
elif k <= len(left) + len(equal):
return pivot
else:
return quick_select(right, k - len(left) - len(equal))
print(quick_select(nums, k))