【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题：翻转对、买卖股票最佳时机、数组中第K个最大/最小元素

# 分治排序算法扩展

class?Solution:

????def?reversePairs(self,?nums:?List[int])?->?int:

????????def?merge(left,?right):

????????????# 统计前面比后面大的翻转对个数

????????????j =?0

????????????for?i in?range(len(left)):

????????????????while?j <?len(right)?and?left[i]?>?2?*?right[j]:

????????????????????j +=?1

????????????????self.count +=?j

????????????# 合并两个有序列表

????????????res =?[]

????????????while??len(left)?>?0?and?len(right)?>?0:

????????????????if?left[0]?<?right[0]:

????????????????????res.append(left.pop(0))

????????????????else:

????????????????????res.append(right.pop(0))

????????????if?left:

????????????????res.extend(left)

????????????if?right:

????????????????res.extend(right)

????????????return?res

????????def?mergeSort(arr):

????????????n =len(arr)

????????????if?n <?2:

????????????????return?arr

????????????middle =?n //?2

????????????left =?arr[:middle]

????????????right =?arr[middle:]

????????????sort_left =?mergeSort(left)

????????????sort_right =?mergeSort(right)

????????????return?merge(sort_left,?sort_right)

????????self.count =?0

????????mergeSort(nums)

????????return?self.count

class?Solution:

????def?maxProfit(self,?prices:?List[int])?->?int:

????????if?not?prices:

????????????return?0

????????minValue =?prices[0]

????????res =?0

????????for?i in?range(1,?len(prices)):

????????????minValue =?min(minValue,?prices[i])

????????????res =?max(res,?prices[i]-minValue)

????????return?res

class?Solution:

????def?findKthLargest(self,?nums:?List[int],?k:?int)?->?int:

????????# 使用快速排序

????????lo =?0

????????hi =?len(nums)?-?1

????????k =?len(nums)?-?k

????????while?lo <=?hi:

????????????p =?self.partition(nums,?lo,?hi)

????????????if?p >?k:

????????????????hi =?p -?1

????????????elif?p <?k:

????????????????lo =?p +?1

????????????else:

????????????????return?nums[p]

????????return?-1

????

????def??partition(self,?nums,?lo,?hi):

????????pivot =?nums[lo]

????????i =?lo

????????j =?hi

????????while?i <?j:

????????????while?i <?j and?nums[j]?>=?pivot:

????????????????j -=?1

????????????nums[i]?=?nums[j]

????????????while?i <?j and?nums[i]?<?pivot:

????????????????i +=?1

????????????nums[j]?=?nums[i]

????????nums[i]?=?pivot

????????return?i

def?partition(nums,?lo,?hi):

????pivot =?nums[lo]

????i =?lo

????j =?hi

????while?i <?j:

????????while?i <?j and?nums[j]?>=?pivot:

????????????j -=?1

????????nums[i]?=?nums[j]

????????while?i <?j and?nums[i]?<?pivot:

????????????i +=?1

????????nums[j]?=?nums[i]

????nums[i]?=?pivot

????return?i

def?getKminnums(nums,?k):

????index =?k -?1

????low =?0

????high =?len(nums)?-?1

????while?low <=?high:

????????p =?partition(nums,?low,?high)

????????if?p >?index:

????????????high =?p -?1

????????elif?p <?index:

????????????low =?p +?1

????????else:

????????????# 输出前k个元素

????????????return?nums[:index+1]