当前位置: 首页 > article >正文

分治(2)——快速搜索算法

欢迎来到博主的专栏:算法解析
博主ID:代码小豪

leetcode215——数组中的第k个最大元素

题目解析

在这里插入图片描述
此类在数组中,寻找第k大,第k小,前k大,前k小的OJ问题,通常我们会称其为topk问题,通常这类问题的解法有以下几种。

  • 1.堆排序,时间复杂度O(NlogN)
  • 2.快速排序+遍历数组,时间复杂度为O(NlogN)+O(N)
  • 3.快速搜索算法:时间复杂度为O(N)

此题我们采用快速搜索算法来解决问题

算法原理

快速搜索算法和快速排序的核心方法都是一致的,即分治法。因此它们的代码写起来会有很多相似一致。比如都要随机取key,也要划分数组。因此在这类已经在分治(1)讲过的内容,博主会简单带过。

第一步,我们可以随机取当前数组中的任意一个元素作为key值。并且将数组分为三部分,即x<key的部分,x=key的部分,x>key的部分(0<=x<=n-1)。关于划分数组的代码,可以参考上一篇文章颜色划分的代码。

完成这一步的数组将会是下面的形式:
在这里插入图片描述

我们假设这三部分的子数组的元素个数为a,b,c。
在这里插入图片描述

由于这个数组在经过一次划分之后,数组并非完全无序。而且是一个大体上升序的数组。因此,绿色部分(x>key)中的所有元素,都是原数组中前c个大的元素,蓝色部分的所有元素,都是原数组中前b+c个大的元素,而红色部分的所有元素,都是原数组中前a+b+c大的元素。

因此我们可以分成下面情况进行讨论:

  • (1)若c>=k,则说明第k个大的数在绿色部分,我们可以继续用快速搜索算法来找到绿色部分的第k大的数。
  • (2)若(1)不成立,且b+c>=k,则说明第k大的数在蓝色部分,由于蓝色部分的值都是固定的key,因此第k大的数就是key,将其返回即可。
  • (3)若(1)、(2)不成立,且a+b+c>=k,则说明第k大的数在红色部分,由于红色部分之前的元素都是前b+c大的数,因此我们要在红色部分找第(k-b-c)大的数。对该部分继续使用快速搜索算法

题解代码

class Solution {
private:
    void _swap(int& lhs,int& rhs){
        int tmp=lhs;
        lhs=rhs;
        rhs=tmp;
    }
    int q_serch(vector<int>nums,int begin,int end,int k){
        if(begin==end) return nums[begin]; 

        int left=begin-1,right=end+1,i=begin;
        int key=randomNum(nums,begin,end);
        while(i<right){//将数组划分成三份
            if(nums[i]<key) _swap(nums[i++],nums[++left]);
            else if(nums[i]==key) i++;
            else _swap(nums[i],nums[--right]);
        }
        int b=right-left-1,c=end-right+1;
        if(c>=k) return q_serch(nums,right,end,k);//第k大的元素在绿色部分
        else if(b+c>=k) return key;//第k大的元素在蓝色部分
        else  return q_serch(nums,begin,left,k-(b+c));//第k大的元素在红色部分
    }
    int randomNum(vector<int>nums,int begin,int end){//在nums的[begin,end]中随机一个元素作为key值
        int keyi=rand()%(end-begin+1)+begin;
        return nums[keyi];
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand((unsigned int)time(nullptr));
        return q_serch(nums,0,nums.size()-1,k);
    }
};

http://www.kler.cn/a/589737.html

相关文章:

  • 51单片机学习记录
  • 时间序列分析的军火库:AutoTS、Darts、Kats、PaddleTS、tfts 和 FancyTS解析
  • 【小项目】四连杆机构的Python运动学求解和MATLAB图形仿真
  • 机器学习--卷积神经网络原理及MATLAB回归实现
  • Docker 使用指南
  • C# WPF编程-画刷(Brush)填充图形对象的颜色或图案
  • SpringBoot3和企业版Splunk集成(附加docker配置)
  • CoreData 调试警告:多个 NSEntityDescriptions 声明冲突的解决
  • 数模AI使用教程(新) 2025.3.17
  • Windows安全日志Defender 的配置被修改5007
  • Python数据可视化——生成数据(一)
  • Python基于Django和协同过滤算法实现电影推荐系统功能丰富版
  • 跟着AI复习一下pytorch原理和操作
  • OpenCV计算摄影学(22)将输入的彩色图像转换为两种风格的铅笔素描效果函数pencilSketch()
  • 嵌入式硬件篇---龙芯GPIO控制
  • CTF WEB题
  • 每日一题--进程与协程的区别
  • 【在校课堂笔记】Python 第5节课 总结
  • axios 和 fetch异同点
  • Java继承与反思,单例模式与静态的思考