列表中第k小的元素

问题描述
给定一个列表和一个整数k，找出列表中第k小的元素并返回它的值。

测试样例

# Input: 
array = [8, 5, 2, 9, 7, 6, 3]
k = 3
#Output: 
5
# 列表中最小的元素是2，次小的元素是3，第3小的元素是5。

内容首发于微信公众号IT信息教室，如果您想学习更多AI相关的技能，欢迎搜索关注或微信扫描下方二维码关注～～

参考代码

class Solution:
    def findKthSmallest(self, array, k):
        position = k - 1
        return self.quickselect(array, 0, len(array)-1, position)
    
    def quickselect(self, array, startIdx, endIdx, position):
        pivot = startIdx
        leftIdx = startIdx + 1
        rightIdx = endIdx
        while leftIdx <= rightIdx:
            if array[leftIdx] > array[pivot] and array[rightIdx] < array[pivot]:
                array[leftIdx], array[rightIdx] = array[rightIdx], array[leftIdx]
            if array[leftIdx] <= array[pivot]:
                leftIdx += 1
            if array[rightIdx] >= array[pivot]:
                rightIdx -= 1
        array[rightIdx], array[pivot] = array[pivot], array[rightIdx]
        if rightIdx == position:
            return array[rightIdx]
        elif rightIdx < position:
            return self.quickselect(array, rightIdx + 1, endIdx, position)
        elif rightIdx > position:
            return self.quickselect(array, startIdx, rightIdx - 1, position)
      
# Test Program
array = [8, 5, 2, 9, 7, 6, 3]
k = 3
result = Solution().findKthSmallest(array, k)
print(result)
# 5