Description
Find the kth smallest number in an unsorted integer array.
Example
Example 1:
Input: [3, 4, 1, 2, 5], k = 3
Output: 3
Example 2:
Input: [1, 1, 1], k = 2
Output: 1
Challenge
An O(nlogn) algorithm is acceptable, if you can do it in O(n), that would be great.
思路：
用快速排序的同时，舍弃掉一半不存在答案的结果， 就可以优化时间复杂度。写代码的时候有几个坑要注意， 一是start, end不能直接用来当指针，因为后续判断区间的时候还要用， 二是在舍弃区间时要注意有三种可能情况，可能在左边，也可能在右边， 还可能在中间左右指针之间，三是如果答案落在右边区间，传递的参数就不是原先的k了， 要变成k-(left -start)
这两个题是类似的就写到一起，唯一的区别就是一个是从大到小排序，另一个是从小到大。
时间复杂度：
O(n)
代码：
网友评论