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

简介: 【经典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

买卖股票的最佳时机3

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天前
|
存储 算法 调度
【数据结构与算法】详解循环队列:基于数组实现高效存储与访问
【数据结构与算法】详解循环队列:基于数组实现高效存储与访问
|
20天前
|
人工智能 算法
图搜算算法分类
图搜索算法是计算机科学中用于遍历或搜索图结构(由节点和边组成的数学结构)的技术,常应用于路径规划、网络分析、人工智能等领域。下面是对几种常见图搜索算法的简要说明:
|
22天前
|
机器学习/深度学习 存储 算法
数据结构与算法:数组的操作
数据结构与算法:数组的操作
|
26天前
|
机器学习/深度学习 分布式计算 算法
在机器学习项目中,选择算法涉及问题类型识别(如回归、分类、聚类、强化学习)
【6月更文挑战第28天】在机器学习项目中,选择算法涉及问题类型识别(如回归、分类、聚类、强化学习)、数据规模与特性(大数据可能适合分布式算法或深度学习)、性能需求(准确性、速度、可解释性)、资源限制(计算与内存)、领域知识应用以及实验验证(交叉验证、模型比较)。迭代过程包括数据探索、模型构建、评估和优化,结合业务需求进行决策。
29 0
|
26天前
|
存储 算法 安全
加密算法概述:分类与常见算法
加密算法概述:分类与常见算法
|
28天前
|
存储 算法 编译器
【数据结构与算法】使用数组实现栈:原理、步骤与应用
【数据结构与算法】使用数组实现栈:原理、步骤与应用
|
29天前
|
存储 算法 Java
Java数据结构与算法:线性数据结构之数组
Java数据结构与算法:线性数据结构之数组
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值