# 【经典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

## TOP K问题

### 数组中的 第K个最大元素

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

### 数组中前K个最小的元素

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]

|
28天前
|

【数据结构与算法】详解循环队列：基于数组实现高效存储与访问
【数据结构与算法】详解循环队列：基于数组实现高效存储与访问
41 1
|
20天前
|

23 0
|
22天前
|

11 0
|
26天前
|

【6月更文挑战第28天】在机器学习项目中，选择算法涉及问题类型识别（如回归、分类、聚类、强化学习）、数据规模与特性（大数据可能适合分布式算法或深度学习）、性能需求（准确性、速度、可解释性）、资源限制（计算与内存）、领域知识应用以及实验验证（交叉验证、模型比较）。迭代过程包括数据探索、模型构建、评估和优化，结合业务需求进行决策。
29 0
|
26天前
|

18 0
|
28天前
|

【数据结构与算法】使用数组实现栈：原理、步骤与应用
【数据结构与算法】使用数组实现栈：原理、步骤与应用
14 0
|
29天前
|

Java数据结构与算法：线性数据结构之数组
Java数据结构与算法：线性数据结构之数组
17 0
|
1月前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-2
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
30 2
|
1月前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-1
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
36 2
|
1月前
|

【LeetCode刷题】二分查找：山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找：山脉数组的峰顶索引、寻找峰值
27 1