快速排序题目&SelectK问题

这篇具有很好参考价值的文章主要介绍了快速排序题目&SelectK问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

力扣75.颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

快速排序题目&SelectK问题,算法

快速排序题目&SelectK问题,算法 

class Solution { //时间复杂度为O(n)
    //其实,变量 zero 相当于我们在三路快速排序算法中的 lt;
    //变量 two 相当于我们在三路快速排序算法中的 gt。
    public void sortColors(int[] nums) {
        // nums[0...zero] == 0, nums[zero + 1, i] == 1, nums[two, n - 1] == 2
        // 定义三个指针:zero、i、two,分别表示0的最右边界、当前处理的元素、2的最左边界
        int zero = -1, i = 0, two = nums.length;
        while(i < two){// 当前处理元素的指针小于2的最左边界时,继续循环
            // 如果当前元素为0,将其与zero右边的元素交换,并将zero和i都向右移动一位
            if(nums[i] == 0){
                zero++;
                swap(nums,zero,i);
                i++;
            }
            // 如果当前元素为2,将其与two左边的元素交换,并将two向左移动一位
            else if (nums[i] == 2){ // 注意此时不需要i右移,因为交换后的元素还需要继续判断
                two --;
                swap(nums, i, two);
            }
            else{ //如果当前元素是1,不需要操作,直接继续向右遍历
                i ++;
            }
        }
    }
    // 交换数组中指定位置的两个元素
    private void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i]= nums[j];
        nums[j] = t;
    }
}


我们首先来封装一个 selectK 的方法。封装好了这个方法以后,这三个问题都可
以快速求解。
我们的 selectK 的接口是这样的:
// 在 arr[l...r] 的范围里求解整个数组的第 k 小元素并返回
// k 是索引,即从 0 开始计算
int selectK(int[] arr, int l, int r, int k, Random rnd)
因为我们的 partition 过程需要随机选取标定点,所以我们还需要传一个 Random(快排的优化)
类的对象 rnd。
定义好函数签名以后,下面我们来书写相应的逻辑。
首先,selectK 的过程,我们就是要执行一遍 partition。在这里,我使用双路快速
排序的 partition。
注意,因为在这个问题中,我们肯定我们处理的数据类型是 int,所以,在代码
中,我不再使用泛型:

private int partition(int[] arr, int l, int r, Random rnd){
    // 生成 [l, r] 之间的随机索引
    int p = l + rnd.nextInt(r - l + 1);
    swap(arr, l, p);
    // arr[l+1...i-1] <= v; arr[j+1...r] >= v
    int i = l + 1, j = r;
    while(true){
    while(i <= j && arr[i] < arr[l])
        i ++;
    while(j >= i && arr[j] > arr[l])
        j --;
    if(i >= j) break;

    swap(arr, i, j);
    i ++;
    j --;
}
    swap(arr, l, j);
    return j;
}
private void swap(int[] arr, int i, int j){
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}

有了 partition,我们的 selectK 的主题逻辑非常简单。

首先,进行 partition,假设结果是 p。我们只需要将 k 和 p 做比较。

  • 如果 k == p,直接返回 arr[p] 即可;
  • 如果 k < p,在 arr[l, p - 1] 的范围继续找,即调用 selectK(arr, l, p - 1, k, rnd);
  • 如果 k > p,在 arr[p + 1, r] 的范围继续找,即调用 selectK(arr, p + 1, r, k, rnd);

就有了下面的代码:

private int selectK(int[] arr, int l, int r, int k, Random rnd){
int p = partition(arr, l, r, rnd);
if(k == p) return arr[p];
if(k < p) return selectK(arr, l, p - 1, k, rnd);
    return selectK(arr, p + 1, r, k, rnd);
}

这样,我们就完成了 select K 的过程。是不是非常简单!

下面,我们用我们写的 select K,先来解决 Leetcode 上第 215 号问题:

这个问题是求第 k 大元素,但是我们的 selectK 求得是第 k 小元素。怎么办?
非常简单,我们只需要在调用 select K 之前,将求第 k 大元素的这个 k,转换成
对应求的是第几小元素对应的索引就好了。
按照题目描述,如果 k 是 1,对应就是要找最大元素,那么相应的我们的
select K 的索引,就是 nums.length - 1。(如果10个数,K=1,第一个最大的数,就是SelectK索引为9的那个的元素)
如果 k 是 nums.length,其实就是求最小元素,那么相应的我们的 selectK 的
索引,就是 0。  (如果10个数,第10个最大的数,就是SelectK索引为0的那个的元素,最小值)
他们之间的转换关系是 nums.length - k。

力扣215.数组中的第K个最大元素 

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

快速排序题目&SelectK问题,算法

快速排序题目&SelectK问题,算法文章来源地址https://www.toymoban.com/news/detail-853896.html

import java.util.Random; //导入Random包
class Solution {
    public int findKthLargest(int[] nums, int k) {
        //只有两行,其他的内容全部复用我们上面实现的 selectK,是不是很酷?
        //我们的SelectK是第K最小元素,所以这里findKthLargest传入下标要处理一下
        //转换关系是 nums.length - k
        Random rnd = new Random();
        return selectK(nums, 0, nums.length - 1, nums.length - k, rnd);
    }

    //有了 partition,我们的 selectK 的主题逻辑非常简单。
    private int selectK(int[] arr, int l, int r, int k, Random rnd){
        //首先,进行 partition,假设返回值结果是 p。我们只需要将 k 和 p 做比较。
        int p = partition(arr, l, r, rnd); 
        //如果 k == p,直接返回 arr[p] 即可;
        if(k == p) return arr[p]; 
        //如果 k < p,在 arr[l, p - 1] 的范围继续找,即调用 selectK(arr, l, p - 1, k, rnd);
        if(k < p) return selectK(arr, l, p - 1, k, rnd); 
        //如果 k > p,在 arr[p + 1, r] 的范围继续找,即调用 selectK(arr, p + 1, r, k, rnd);
        return selectK(arr, p + 1, r, k, rnd);
}
    private int partition(int[] arr, int l, int r, Random rnd){
        // 生成 [l, r] 之间的随机索引
        int p = l + rnd.nextInt(r - l + 1);
        swap(arr, l, p);
        // arr[l+1...i-1] <= v; arr[j+1...r] >= v
        int i = l + 1, j = r;
        while(true){
            while(i <= j && arr[i] < arr[l])
                i ++;
            while(j >= i && arr[j] > arr[l])
                j --;
            if(i >= j) break;
            swap(arr, i, j);
            i ++;
            j --;
        }
        swap(arr, l, j);
        return j;
    }

    //数组指定索引,两数交换
    private void swap(int[] arr, int i, int j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

到了这里,关于快速排序题目&SelectK问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【排序算法】归并排序与快速排序

           🔥🔥 欢迎来到小林的博客!!       🛰️博客主页:✈️小林爱敲代码       🛰️博客专栏:✈️ 算法训练笔记       🛰️社区 :✈️ 进步学堂       🛰️欢迎关注:👍点赞🙌收藏✍️留言 今天给大家分享两种排序,一种是

    2024年01月19日
    浏览(39)
  • 算法基础15 —— 分治算法(归并排序 + 快速排序)

    分治法的基本概念、思想 分治法是一种很重要的算法。 字面解释,分治分治,分而治之。就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。 不难发现,分

    2024年02月03日
    浏览(52)
  • 排序算法1:冒泡排序、快速排序、插入排序

    排序算法:交换类排序,插入类排序、选择类排序、归并类排序 交换类排序:冒泡排序、快速排序 一、冒泡排序  时间复杂度:内层是ji,外层是从0到n-1,运行的总次数是1+2+3+4+...+n-1,即O() 空间复杂度:O(1),没有使用额外空间,不会因为n的变化而变化 如果数组本身有序,最

    2024年02月21日
    浏览(45)
  • 【排序算法(三)】交换排序(冒泡排序&&快速排序)

    ​ ​📝个人主页:@Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯 长路漫漫浩浩,万事皆有期待 上一篇博客:【排序算法(二)】选择排序(直接选择排序堆排序) 冒泡排序属于交换排序,所谓 交换排序 就是就是根据序列中两个记录

    2023年04月22日
    浏览(43)
  • 【算法】排序——选择排序和交换排序(快速排序)

     ========================================================================= 主页点击直达: 个人主页 我的小仓库: 代码仓库 C语言偷着笑: C语言专栏 数据结构挨打小记:初阶数据结构专栏 Linux被操作记:Linux专栏 LeetCode刷题掉发记:LeetCode刷题 算法头疼记:算法专栏  =========================

    2024年02月08日
    浏览(45)
  • 【算法系列 | 5】深入解析排序算法之——快速排序

    你只管努力,其他交给时间,时间会证明一切。 文章标记颜色说明: 黄色 :重要标题 红色 :用来标记结论 绿色 :用来标记一级论点 蓝色 :用来标记二级论点 决定开一个算法专栏,希望能帮助大家很好的了解算法。主要深入解析每个算法,从概念到示例。 我们一起努力

    2024年02月08日
    浏览(46)
  • 排序算法二 归并排序和快速排序

    目录 归并排序 快速排序 1 挖坑法​编辑 2 Hoare法 快排的优化 快排的非递归方法 七大排序算法复杂度及稳定性分析 归并排序是建立在归并操作上的一种有效的排序算法,将以有序的子序列合并,得到完全有序的序列,即先使每个子序列有序,在使子序列段间有序.若将两个有序的

    2024年02月07日
    浏览(40)
  • 排序算法:快速排序(非递归)

    ! 先赞后看,养成习惯!!!^ _ ^3 ❤️ ❤️ ❤️ 码字不易,大家的支持就是我坚持下去的动力。点赞后不要忘了 关注 我哦! 所属专栏:排序算法 思路如下: 为什么要建立栈呢? 建立栈是为了让每次排序的区间进去,然后后面便于取出 这里用了之前的快速排序的一个格式

    2024年03月26日
    浏览(43)
  • 排序算法:快速排序(递归)

    所属专栏:C++初阶 引言:这里所说的快速排序有三种,第一种是 霍尔大佬 自创的,还有一种叫做 挖坑法 ,另外一种叫 前后指针法 1.这里我们先把中间值定位数组中的首元素的值,设为key变量, 大于key的放右边,小于key的放左边 2.定义left为从数组0下标开始找大于key的数,如

    2024年04月09日
    浏览(45)
  • 快速排序-排序算法

    算法思想 快速排序采用的仍然是 分治 的思想。 Step1.每次在无序的序列中选取一个基准数。 Step2.然后将大于和小于基准数的元素分别放置于基准数两边。(前面部分的元素均小于或等于基准数,后面部分均大于或等于基准数) Step3.然后采用分治法(递归)分别对两侧部分重

    2024年01月25日
    浏览(31)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包