python | #寻找第K大#

WC130 寻找第K大

思路：快速排序后

# -*- coding:utf-8 -*-

class Solution:
    def findKth(self, a, n, K):
        # write code here
        a_sort = self.quick_sort(a, 0, n-1)
        return a_sort[n-K]

    def quick_sort(self,l,left,right):
        if left >= right:
            return 
        low = left
        high = right
        point = l[low] 
        while low < high:
            while low < high and point<= l[high]:
                high -= 1
            while low <high and point >=l[low]:
                low += 1
            self.swap(l, low, high)
        self.swap(l, left, low)
        self.quick_sort(l,left,low-1)
        self.quick_sort(l,low+1,right)
        return l 
    def swap(self,l,i,j):
        tem = l[i]
        l[i] = l[j]
        l[j] = tem

偷懒解法

class Solution:
    def findKth(self, a, n, K):
        # write code here
        a.sort()
        return a[n-K]

二分+快排：当右边有k-1个值大于p，左边n-k个值小于p，返回P即可

# -*- coding:utf-8 -*-

class Solution:
    def partsort(self, l, left, right):
        point = l[left]
        low = left
        high = right
        point = l[low] 
        while low < high:
            while low < high and point<= l[high]:
                high -= 1
            while low <high and point >=l[low]:
                low += 1
            self.swap(l, low, high)
        self.swap(l, left, low)
        return low
    def swap(self,l,i,j):
        tem = l[i]
        l[i] = l[j]
        l[j] = tem


    def findKth(self, a, n, K):
        # write code here
        l = 0
        r = n - 1
        div = self.partsort(a, l, r)
        while(div != n-K): #只有当刚好右边有k-1个大于div处的值时，返回此时的值，否则只需对一边排序
            if div < n-K:
                div = self.partsort(a, div + 1, r)
            else:
                div = self.partsort(a, l, div - 1)
        return a[div]