洛谷_P1923 【深基9.例4】求第 k 小的数

洛谷_P1923 【深基9.例4】求第 k 小的数_python写法

本文主要是介绍洛谷_P1923 【深基9.例4】求第 k 小的数_python写法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

哪位大佬可以出一下这个的题解？？？？？话说蓝桥杯可以用numpy库吗？？？？？？

这道题有一个很简单的思路就是排序完成之后再访问。

but有很大的问题，压根就不能通过，那怎么办呢？

百度一下找到答案，看到网上分享说这道题应该用分治+快速排序的算法，那我们首先来学习一下这两个是个什么事儿。

快速排序【分治思想 + python实现含图解】_python分治算法排序-CSDN博客

1.分治是一种思想

分治就是将一个大问题分成若干个小问题去处理，当每一个小问题都得到了解决那么一整个问题也算是得到了解决，

2.快速排序

那我这部分的笔记就是参考上面那篇博客来的，感觉这篇笔记很适合我们小白学习。

这篇笔记的图解就非常详细。

看完图解之后差不多就可以理解快速排序到底是快在哪里。

那快速排序的代码怎么完成呢？我们如何完成上图的一系列操作呢。其实快速排序最重要的一个点在于列表中每一个元素都有一个应有的位置，怎么找到这个正确的位置就是我们需要解决的。现在我们捋一下思路。

快速排序思路（升序为例）：

根绝上面的图解我们知道，所谓每一个元素自己正确的位置意思是这个元素左边的元素都会小于他，右边的元素都会大于他，当每一个元素都满足这样的要求那么说明整个列表排序完成。

def quick_sort(nums, start, end):if start >= end:returnpivot, l, r = nums[start], start, endwhile l < r:while nums[r] >= pivot and l < r:r -= 1while nums[l] <= pivot and l < r:l += 1nums[l], nums[r] = nums[r], nums[l]nums[start], nums[r] = nums[r], nums[start]

5.分治模块
1）此时，下标为 r 的元素（就是之前选的 pivot）已经排在了正确的位置，左边都 <= pivot，右边都 >= pivot，那么我们再对左半部分 nums 和右半部分 nums 分别进行排序即可。
2）左边的起始下标仍为 start，终止下标变成了 r-1，因为 nums[r] 已经排好序不用再加上了；右边同理，起始为 r+1，终止为 end。
3）如果最后一轮排序找到的 r 就等于列表起始下标start，或者 r 就等于列表终止下标end，那么显然start > r-1 或者 r+1>end，则下一次的quick_sort 中有 start>end，所以终止条件中会有出现 start>end 时直接返回的这种情况。

3.代码

def quick_sort(nums, start, end):if start >= end:returnpivot, l, r = nums[start], start, endwhile l < r:while nums[r] >= pivot and l < r:r -= 1while nums[l] <= pivot and l < r:l += 1nums[l], nums[r] = nums[r], nums[l]nums[start], nums[r] = nums[r], nums[start]quick_sort(nums, start, r - 1)quick_sort(nums, r + 1, end)def f(nums):quick_sort(nums, 0, len(nums) - 1)return numsnums1 = [3, 2, 3, 1, 2, 4, 5, 5, 6]
print(f(nums1))

4.题解

错了但是我不知道错在哪里了

n, k = map(int, input().split(' '))
x = list(map(int, input().split(' ')))def qsort(l, r):i, j, mid = l, r, x[(l + r) // 2]while i <= j:while x[j] > mid:j -= 1while x[i] < mid:i += 1if i <= j:x[i], x[j] = x[j], x[i]i += 1j -= 1# 快排后数组被划分为三块： l<=j<=i<=rif k <= j:qsort(l, j)elif i <= k:# 在右区间只需要搜右区间qsort(i, r)else:# 如果在中间区间直接输出print(x[k])qsort(0, n - 1)