蓝桥14

淩亂°似流年 2023-01-11 13:02 152阅读 0赞

# 一数据中第K个最大元素 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70]

*      快排
 *  每次迭代判断第一个数有多少数比它小它就是第几位，直接安插在固定位置
 *  每次迭代都能令一个数到达最终位置
 *  复杂度O（n）

class Solution:
        def findKthLargest(self, nums: List[int], k: int) -> int:
            # 快排
            def quicksort(arr): # 参数不必加self
                if len(arr) < 2:
                    return arr
                central_ele = arr[0]
                smaller_sub_arr = [e for e in arr[1:] if e <= central_ele] # ‘=’不要丢了
                larger_sub_arr = [e for e in arr[1:] if e > central_ele]
                return quicksort( smaller_sub_arr) + [central_ele] + quicksort(larger_sub_arr)
            sorted_nums = quicksort(nums)
            # 返回倒数第k个数
            return sorted_nums[-k]

# 二存在重复元素 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 1]

*  判断set后长度是否变化

class Solution:
        def containsDuplicate(self, nums: List[int]) -> bool:
            return len(nums)!=len(set(nums))

# 三二叉搜索数中第K个最小元素 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 2]

*  二叉树遍历方法有三种，前序，中序和后序
 *  因为这是二叉搜索数，大小时按左中右排序的，所以我们使用中序遍历
 *  遍历中止条件时这个数是第K小的，我们找到一个最小的就去除，k-1，到最后k=0即可

class Solution:
        def kthSmallest(self, root: TreeNode, k: int) -> int:
            stack = []
            while True:
                while root:
                    stack.append(root)
                    root = root.left
                root = stack.pop()
                k -= 1
                if k == 0: return root.val
                root = root.right

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210126230010114.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210126230314226.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210126230423371.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA==,size_16,color_FFFFFF,t_70