benym的知识笔记 benym的知识笔记
🦮首页
  • Java

    • Java-基础
    • Java-集合
    • Java-多线程与并发
    • Java-JVM
    • Java-IO
  • Python

    • Python-基础
    • Python-机器学习
  • Kafka
  • Redis
  • MySQL
  • 分布式事务
  • Spring

    • SpringIOC
    • SpringAOP
🦌设计模式
  • 剑指Offer
  • LeetCode
  • 排序算法
🐧实践
  • Rpamis

    • Utils
    • Exception
    • Security
  • 归档
  • 标签
  • 目录
🦉里程碑
🐷关于
GitHub (opens new window)

benym

惟其艰难,才更显勇毅🍂惟其笃行,才弥足珍贵
🦮首页
  • Java

    • Java-基础
    • Java-集合
    • Java-多线程与并发
    • Java-JVM
    • Java-IO
  • Python

    • Python-基础
    • Python-机器学习
  • Kafka
  • Redis
  • MySQL
  • 分布式事务
  • Spring

    • SpringIOC
    • SpringAOP
🦌设计模式
  • 剑指Offer
  • LeetCode
  • 排序算法
🐧实践
  • Rpamis

    • Utils
    • Exception
    • Security
  • 归档
  • 标签
  • 目录
🦉里程碑
🐷关于
GitHub (opens new window)
  • 剑指Offer

    • 01背包问题详解
    • LeetCode-面试题17-打印从1到最大的n位数
    • LeetCode-面试题03-不修改数组找出重复的数字
    • LeetCode-面试题03-数组中重复的数字
    • LeetCode-面试题04-二维数组中的查找
    • LeetCode-面试题05-替换空格
    • LeetCode-面试题06-从尾到头打印链表
    • LeetCode-面试题09-用两个栈实现队列
    • LeetCode-面试题10-1-斐波那契数列
    • LeetCode-面试题10-2-青蛙跳台阶
    • LeetCode-面试题11-旋转数组的最小数字
    • LeetCode-面试题13-机器人的运动范围
    • LeetCode-面试题14-1-剪绳子
    • LeetCode-面试题14-2-剪绳子(大数)
    • LeetCode-面试题15-二进制中1的个数
    • LeetCode-面试题16-数值的整数次方
    • LeetCode-面试题18-删除链表的节点
    • LeetCode-面试题19-正则表达式匹配
    • LeetCode-面试题20-表示数值的字符串
    • LeetCode-面试题21-调整数组顺序使奇数位于偶数前面
    • LeetCode-面试题22-链表中倒数第k个节点
    • LeetCode-面试题24-反转链表
    • LeetCode-面试题25-合并两个排序的链表
    • LeetCode-面试题26-树的子结构
    • LeetCode-面试题27-二叉树的镜像
    • LeetCode-面试题29-顺时针打印矩阵
    • LeetCode-面试题31-栈的压入弹出序列
    • LeetCode-面试题32-1-从上到下打印二叉树
    • LeetCode-面试题32-2-从上到下打印二叉树
    • LeetCode-面试题32-3-从上到下打印二叉树
    • LeetCode-面试题35-复杂链表的复制
    • LeetCode-面试题36-二叉搜索树与双向链表
    • LeetCode-面试题37-序列化二叉树
    • LeetCode-面试题38-字符串的排列
    • LeetCode-面试题39-数组中出现次数超过一半的数字
    • LeetCode-面试题40-最小的k个数
    • LeetCode-面试题41-数据流中的中位数
    • LeetCode-面试题42-连续子数组的最大和
    • LeetCode-面试题43-1到n整数中1出现的次数
    • LeetCode-面试题44-数字序列中某一位的数字
    • LeetCode-面试题45-把数组排成最小的数
    • LeetCode-面试题47-礼物的最大价值
    • LeetCode-面试题48-最长不含重复字符的子字符串
    • LeetCode-面试题49-丑数
    • LeetCode-面试题50-第一次只出现一次的字符
    • LeetCode-面试题51-数组中的逆序对
    • LeetCode-面试题53-1-在排序数组中查找数字I
    • LeetCode-面试题33-二叉搜索树的后序遍历序列
    • LeetCode-面试题54-二叉搜索树的第k大节点
    • LeetCode-面试题55-1-二叉树的深度
    • LeetCode-面试题12-矩阵中的路径
    • LeetCode-面试题30-包含min函数的栈
    • LeetCode-面试题34-二叉树中和为某一值的路径
    • LeetCode-面试题46-把数字翻译成字符串
    • LeetCode-面试题55-2-平衡二叉树
    • LeetCode-面试题56-1-数组中数字出现的次数
    • LeetCode-面试题56-2-数组中数字出现的次数2
    • LeetCode-面试题57-和为s的两个数字
    • LeetCode-面试题58-1-翻转单词顺序
    • LeetCode-面试题58-2-左旋转字符串
    • LeetCode-面试题59-2-队列的最大值
    • LeetCode-面试题60-n个骰子的点数
    • LeetCode-面试题61-扑克牌中的顺子
    • LeetCode-面试题62-圆圈中最后剩下的数字
    • LeetCode-面试题63-股票的最大利润
    • LeetCode-面试题64-求1+2+到+n
    • LeetCode-面试题65-不用加减乘除做加法
    • LeetCode-面试题66-构建乘积数组
    • LeetCode-面试题67-把字符串转化成整数
    • LeetCode-面试题68-1-二叉搜索树的最近公共祖先
    • LeetCode-面试题68-2-二叉搜索树的最近公共祖先
    • LeetCode-面试题07-重建二叉树
    • LeetCode-面试题52-两个链表的第一个公共节点
    • LeetCode-面试题53-2-0到n-1中缺失的数字
    • LeetCode-面试题57-2-和为s的连续正数序列
    • LeetCode-面试题59-1-滑动窗口的最大值
    • LeetCode-面试题28-对称的二叉树
  • LeetCode

    • LeetCode-54-螺旋矩阵
    • LeetCode-67-二进制求和
    • LeetCode-83-删除排序链表中的重复元素
    • LeetCode-415-字符串相加
    • LeetCode-498-对角线遍历
    • LeetCode-724-寻找数组的中心索引
    • 动态规划问题——最长上升子序列(LIS)(一)
    • 动态规划问题——最长上升子序列(LIS)(二)
    • 动态规划问题——最长上升子序列(LIS)(三)
    • LeetCode-144-二叉树的前序遍历
    • LeetCode-94-二叉树的中序遍历
    • LeetCode-145-二叉树的后序遍历
    • LeetCode-53-最大子序和
    • LeetCode-392-判断子序列
    • LeetCode-303-区域和检索-数组不可变
    • LeetCode-2-两数相加
    • LeetCode-3-无重复字符的最长字串
    • LeetCode-4-寻找两个正序数组的中位数
    • LeetCode-5-最长回文字串
    • LeetCode-11-盛最多水的容器
    • LeetCode-15-三数之和
    • LeetCode-17-电话号码的字母组合
    • LeetCode-19-删除链表的倒数第N个节点
    • LeetCode-20-有效的括号
    • LeetCode-21-合并两个有序链表
    • LeetCode-22-括号生成
    • LeetCode-23-合并K个排序链表
    • LeetCode-31-下一个排列
    • LeetCode-32-最长有效括号
    • LeetCode-33-搜索旋转排序数组
    • LeetCode-34-在排序数组中查找元素的第一个和最后一个位置
    • LeetCode-39-组合总数
    • LeetCode-46-全排列
    • LeetCode-47-全排列2
    • LeetCode-51-N皇后
    • LeetCode-55-跳跃游戏
    • LeetCode-56-合并区间
    • LeetCode-62-不同路径
    • LeetCode-64-最小路径和
    • LeetCode-70-爬楼梯
    • LeetCode-72-编辑距离
    • LeetCode-75-颜色分类
    • LeetCode-76-最小覆盖字串
    • LeetCode-77-组合
    • LeetCode-78-子集
    • LeetCode-84-柱状图中最大的矩形
    • LeetCode-102-二叉树的层序遍历
    • LeetCode-104-二叉树的最大深度
    • LeetCode-105-从前序与中序遍历构造二叉树
    • LeetCode-107-二叉树的层次遍历2
    • LeetCode-114-二叉树展开为链表
    • LeetCode-121-买卖股票的最佳时机
    • LeetCode-128-最长连续序列
    • LeetCode-136-只出现一次的数字
    • LeetCode-142-环形链表2
    • LeetCode-143-重排链表
    • LeetCode-146-LRU缓存机制
    • LeetCode-152-乘积最大子数组
    • LeetCode-198-打家劫舍
    • LeetCode-199-二叉树的右视图
    • LeetCode-206-反转链表
    • LeetCode-207-课程表
    • LeetCode-215-数组中的第K个最大元素
      • LeetCode-215-数组中的第K个最大元素
        • 解题思路
        • Java代码
        • Python代码
        • Java代码2
    • LeetCode-221-最大正方形
    • LeetCode-226-翻转二叉树
    • LeetCode-236-二叉树的最近公共祖先
    • LeetCode-279-完全平方数
    • LeetCode-287-寻找重复数
    • LeetCode-300-最长上升子序列
    • LeetCode-309-最佳买卖股票时机含冷冻期
    • LeetCode-322-零钱兑换
    • LeetCode-328-奇偶链表
    • LeetCode-347-前K个高频元素
    • LeetCode-394-字符串解码
    • LeetCode-406-根据身高重建队列
    • LeetCode-413-等差数列划分
    • LeetCode-416-分割等和子集
    • LeetCode-438-找到字符串中所有字母异位词
    • LeetCode-448-找到所有数组中消失的数字
    • LeetCode-461-汉明距离
    • LeetCode-494-目标和
    • LeetCode-538-把二叉搜索树转换为累加树
    • LeetCode-543-二叉树的直径
    • LeetCode-560-和为K的子数组
    • LeetCode-567-字符串的排列
    • LeetCode-581-最短无序连续子数组
    • LeetCode-617-合并二叉树
    • LeetCode-704-二分查找
    • LeetCode-739-每日温度
    • LeetCode-747-至少是其他数字两倍的最大数
    • LeetCode-890-查找和替换模式
    • LeetCode-1143-最长公共子序列
    • LeetCode-1247-交换字符使得字符串相同
    • LeetCode-1367-二叉树中的列表
    • LeetCode-字符串排序
    • LeetCode-面试题02.02-返回倒数第k个节点
    • LeetCode-面试题17.16-按摩师
    • 获取满足指数的最长字符串
    • 数组的最多素数个数
    • 最小字典序字符串
    • LeetCode-1-两数之和
    • LeetCode-16-最接近的三数之和
    • LeetCode-679-24点游戏
    • LeetCode-141-环形链表
    • LeetCode-155-最小栈
    • LeetCode-160-相交链表
    • 判断一棵二叉树是否为二叉搜索树和完全二叉树
    • LeetCode-169-多数元素
    • LeetCode-234-回文链表
    • LeetCode-238-除自身以外数组的乘积
    • LeetCode-283-移动零
    • LeetCode-338-比特位计数
    • LeetCode-797-所有可能的路径
  • 排序算法

    • 常见排序算法总结
    • 冒泡排序
    • 基数排序
    • 堆排序
    • 希尔排序
    • 归并排序
    • 快速排序
    • 插入排序
    • 桶排序
    • 选择排序
  • 算法
  • LeetCode
benym
2020-06-24
目录

LeetCode-215-数组中的第K个最大元素

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

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
1
2
1
2

示例2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
1
2
1
2

说明:

你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

# 解题思路

方法1、优先队列:

首先想到的是给数组进行排序,排序之后就很容易找到第k个最大的元素

那么有没有不排序的方法,自然就会想到建立堆来进行操作

我们可以建立一个大顶堆,最大的数在建堆的过程中排最上面,一次遍历就能完成数组从大到小的构建

寻找排序之后的第k个最大的元素,也就是寻找大顶堆的正序第k个元素

之后一直弹出到k-1为止,下一个位置就是第k个最大的元素

方法2、暴力破解:

排序之后,倒置一下,第k-1个位置就是第k个最大的元素,不倒置就是nums.length-k个位置

方法3、快速选择:

摘自LeetCode官方题解 (opens new window)

就像快速排序那样,本算法也是 Tony Hoare 发明的,因此也被称为 Hoare选择算法。

本方法大致上与快速排序相同。简便起见,注意到第 k 个最大元素也就是第 N - k 个最小元素,因此可以用第 k 小算法来解决本问题。

首先,我们选择一个枢轴,并在线性时间内定义其在排序数组中的位置。这可以通过 划分算法 的帮助来完成。

为了实现划分,沿着数组移动,将每个元素与枢轴进行比较,并将小于枢轴的所有元素移动到枢轴的左侧。

这样,在输出的数组中,枢轴达到其合适位置。所有小于枢轴的元素都在其左侧,所有大于或等于的元素都在其右侧。

这样,数组就被分成了两部分。如果是快速排序算法,会在这里递归地对两部分进行快速排序。

而在这里,由于知道要找的第 N - k 小的元素在哪部分中,我们不需要对两部分都做处理。

最终的算法十分直接了当 :

  • 随机选择一个枢轴。

  • 使用划分算法将枢轴放在数组中的合适位置 pos。将小于枢轴的元素移到左边,大于等于枢轴的元素移到右边。

  • 比较 pos 和 N - k 以决定在哪边继续递归处理。

# Java代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        if (len == 1) {
            return nums[0];
        }
        if (len <= 2) {
            Arrays.sort(nums);
            return nums[len - k];
        }
        Queue<Integer> queue = new PriorityQueue<>((v1,v2)->v2-v1);
        for (int i = 0; i < len; i++) {
            queue.add(nums[i]);
        }
        int i=0;
        while (!queue.isEmpty()&&i<k-1){
            queue.poll();
            i++;
        }
        return queue.poll();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# Python代码

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort(reverse=True)
        return nums[k-1]
1
2
3
4
1
2
3
4

# Java代码2

class Solution {
    int[] nums;

    public void swap(int a, int b) {
        int tmp = this.nums[a];
        this.nums[a] = this.nums[b];
        this.nums[b] = tmp;
    }


    public int partition(int left, int right, int pivot_index) {
        // 优化之后的快排,比枢轴元素大的理论应该放右边,但右边这部分甚至不需要排序
        // 只需要找到N-k个位置就可以了
        int pivot = this.nums[pivot_index];
        // 1. 移动枢轴到最右
        swap(pivot_index, right);
        int store_index = left;

        // 2. 移动所有小的元素到枢轴左边
        for (int i = left; i <= right; i++) {
            if (this.nums[i] < pivot) {
                swap(store_index, i);
                store_index++;
            }
        }

        // 3. 还原枢轴到最终位置,左边的元素全部比他小
        swap(store_index, right);

        return store_index;
    }

    public int quickselect(int left, int right, int k_smallest) {
        if (left == right) // 如果list只包含一个元素
            return this.nums[left];  // 则返回这个元素

        // 选择一个随机的枢轴
        Random random_num = new Random();
        int pivot_index = left + random_num.nextInt(right - left);

        pivot_index = partition(left, right, pivot_index);

        // 枢轴在N-k小的位置上,比较pos和N-k
        if (k_smallest == pivot_index)
            return this.nums[k_smallest];
            // 左递归
        else if (k_smallest < pivot_index)
            return quickselect(left, pivot_index - 1, k_smallest);
        // 右递归
        return quickselect(pivot_index + 1, right, k_smallest);
    }

    public int findKthLargest(int[] nums, int k) {
        this.nums = nums;
        int size = nums.length;
        // 第k个最大的元素,也就是第N-k个最小的元素
        return quickselect(0, size - 1, size - k);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
编辑 (opens new window)
#数组#Java#Python#Medium#LeetCode
上次更新: 2022/11/18, 11:15:10
LeetCode-207-课程表
LeetCode-221-最大正方形

← LeetCode-207-课程表 LeetCode-221-最大正方形→

最近更新
01
SpringCache基本配置类
05-16
02
DSTransactional与Transactional事务混用死锁场景分析
03-04
03
Rpamis-security-原理解析
12-13
更多文章>
Theme by Vdoing | Copyright © 2018-2024 benym | MIT License
 |   |   | 
渝ICP备18012574号 | 渝公网安备50010902502537号
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式