找第k 大的数

题解:

• 找第 K 大数，基于比较的排序的方法时间复杂度为 O(n),数组元素无区间限定，故无法使用线性排序。
• 由于只是需要找第 K 大数，这种类型的题通常需要使用快排的思想解决。这里比较基准值最后的位置的索引值和 K 的大小关系即可递归求解。

# Find K-th largest element in an array.

# Example
# In array [9,3,2,4,8], the 3rd largest element is 4.

# In array [1,2,3,4,5], the 1st largest element is 5,
# 2nd largest element is 4, 3rd largest element is 3 and etc.

# Note
# You can swap elements in the array

# Challenge
# O(n) time, O(1) extra memory.

def partition(l, left, right):
    middle = left
    while(left < right):
        # 高指针先走
        while not l[right] <= l[middle] and left < right:
            right -= 1
        while not l[left] > l[middle] and left < right:
            left += 1
        l[left], l[right] = l[right], l[left]
    # 交换中轴元素
    l[middle], l[right] = l[right], l[middle]
    return left


def quickSort(l, left, right,k):
    if left >= right:
        return -1
    m = partition(l, left, right)
    print('ls {}  l {}  m {}  r {}'.format(l, l[left], l[m], l[right]))
    if k == m:
        return k
    if k > m :
        quickSort(l, m + 1, right,k)
    else :
        quickSort(l, left, m - 1,k)
    


def kThLargestItem(l,k):
    quickSort(l,0,len(l)-1,k)
    print(l[k])



l = [5, 4, 2, 1, 3, 9]
kThLargestItem(l,5)
# quickSort(l, 0, len(l) - 1)
# print(' return_list {}'.format(l))

问题：之前的算法没有考虑到边界条件，即数组中是否有重复数字
问题的解决： 在排序之前去重？