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

分治—快速选择算法

在这里插入图片描述

文章目录

    • 🍇215.数组中的第K个最大元素
      • 🍈1. 题目
      • 🍉2. 算法原理
      • 🍊3. 代码实现
    • 🍋LCR 159. 库存管理 III
      • 🍌1. 题目
      • 🍍2. 算法原理
      • 🥭代码实现

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

🍈1. 题目

题目链接:215. 数组中的第K个最大元素 - 力扣(LeetCode)

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

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

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

示例 1:

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

示例 2:

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

提示:

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

🍉2. 算法原理

解法一:优先级队列(堆)

一般看到第k个什么什么元素,基本都是采用堆来解决,STL里面内置了堆,也就是priority_queue优先级队列,如果是竞赛或者是考试,可以直接用,如果是平时训练,可以自己手搓一个出来。

解法二:快速选择算法(快排)

快速选择算法是基于快排的

快排的核心思路:从数组里面随机选择一个基准元素,将数组分为三部分,即:>key==key<key

将数组分为三个区域之后,我们只需要看这个第k大的元素落在哪个区间即可,那如何确定第k大的元素在哪个区域,也是三种情况:

  • 设左边区间的元素个数为a个,中间区域的元素为b个,右边区间的元素个数为c

    1. c >= k,又区间都是大元素,我们看看有几个大元素,就能知道,第k个是不是在这个区间内,即[right,l]
    2. 当第一个条件不成立时,我们去中间区域找,也就是b+c >= k,在这个区域直接返回即可
    3. 上述两个条件都不成立的情况下,那我们只能去左侧区域[l,left]寻找,这时候要找的就是第k-b-c大的元素了

    image-20231203082854930

🍊3. 代码实现

堆:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        int n = nums.size();
        buildMaxHeap(nums, n);
        for(int i=0;i<k-1;i++)
        {
            swap(nums[0],nums[n-1-i]);
            Adjustdown(nums,n-1-i,0);
        }
        return nums[0];
    }

    void buildMaxHeap(vector<int>& nums , int sz)
    {
        for(int i = (sz - 1 -1)/2; i>=0; i--)
        {
            Adjustdown(nums,sz,i);
        }
    }

    void Adjustdown(vector<int>& nums, int sz, int parent)
    {
        int child = parent*2+1;	//默认左孩子大
        while(child<sz)
        {
            if(child+1 < sz && nums[child] < nums[child+1])
            {
                child++;
            }
            if(nums[child] >nums[parent])
            {
                swap(nums[child],nums[parent]);
                parent = child;
                child = parent*2+1;
            }
            else    break;
        }
    }
};

快速选择:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k)
    {
        srand(time(NULL));
        return quickSort(nums,0,nums.size()-1,k);
    }

    int quickSort(vector<int>& nums, int l, int r, int k)
    {
        if(l == r)  return nums[l];

        int key = getRandom(nums, l, r);
        //数组分为三部分
        int i = l, left = l-1, right = r+1;
        while(i<right)
        {
            if(nums[i] < key)   swap(nums[++left],nums[i++]);
            else if(nums[i] > key)  swap(nums[--right],nums[i]);
            else    i++;
        }

        //查看k在哪个区间
        int c = r - right + 1,
            b = right - left -1;
        if(c >= k)  return quickSort(nums,right,r,k);
        else if(b+c >= k)   return key;
        else    return quickSort(nums,l,left,k-b-c);
    }

    int getRandom(vector<int>& nums, int l, int r)
    {
        return nums[rand()%(r - l + 1) + l];
    }
};

运行结果:

image-20231203085517953

🍋LCR 159. 库存管理 III

🍌1. 题目

题目链接:LCR 159. 库存管理 III

仓库管理员以数组 stock 形式记录商品库存表,其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量,返回 顺序不限

示例 1:

输入:stock = [2,5,7,4], cnt = 1
输出:[2]

示例 2:

输入:stock = [0,2,3,6], cnt = 2
输出:[0,2][2,0]

提示:

  • 0 <= cnt <= stock.length <= 10000
  • 0 <= stock[i] <= 10000

🍍2. 算法原理

这题就和上面这题差不多,这个是求最小的几个元素,顺序不限,解法很多

解法一:排序

直接排升序,然后返回前k个元素即可,时间复杂度O(N*logN)

解法二:堆

建一个大小为k的大根堆,将数据丢进这个堆,最后堆里面的元素就是我们要找的元素,时间复杂度O(N*logK)

详情可以看此篇文章数据结构——二叉树的3.3Top-K内容

解法三:快速选择算法

依旧是快排的核心思想:选取基准元素+数组分三块,时间复杂度为O(N)

还是这张图:

image-20231203092709344

🥭代码实现

class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt)
    {
        srand(time(NULL));
        quickSort(stock, 0, stock.size()-1, cnt);
        return {stock.begin(),stock.begin()+cnt};
    }

    void quickSort(vector<int>& nums ,int l, int r, int k)
    {
        if(l >= r)  return;

        int key = getRandom(nums,l,r);
        int left = l-1,
            right = r+1,
            i = l;

        while(i<right)
        {
            if(nums[i] < key)   swap(nums[++left],nums[i++]);
            else if(nums[i] > key)  swap(nums[--right],nums[i]);
            else    i++;
        }

        //[l,left] [left+1,right-1] [right,r]
        int a = left - l + 1,
            b = right - left - 1;
        if(a > k)   quickSort(nums,l,left,k);
        else if(a+b >= k)    return;
        else    quickSort(nums,right,r,k-a-b);
    }

    int getRandom(vector<int>&  nums, int l, int r)
    {
        return nums[rand() % (r-l+1) + l];
    }
};

运行结果:

image-20231203093923751

运行结果:
在这里插入图片描述


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

相关文章:

  • 【专题】计算机网络之网络层
  • Android音频架构
  • Vue 3 介绍及应用
  • 32位、64位、x86与x64:深入解析计算机架构
  • ubuntu20.04安装FLIR灰点相机BFS-PGE-16S2C-CS的ROS驱动
  • Android 配置默认输入法
  • Linux DataEase数据可视化分析工具本地部署与远程访问
  • 物流实时数仓ODS层——Mysql到Kafka
  • SpringBoot第56讲:SpringBoot集成文件 - 集成EasyExcel之Excel导入导出
  • 学嵌入式,已经会用stm32做各种小东西了,下一步是什么
  • 【预测工具】不须编码的预测和数据可视化工具
  • React自定义Hook之useModel hook
  • 图帕斯TruPulse激光测距仪测高仪维修TP360B TP200
  • 陪玩行业引流不再成难题?“他”到底是怎么做到的
  • 认识Docker
  • Jvm常见问题
  • AI聊天 AI绘画 AI视频 AI制作PPT
  • [Unity数据管理]自定义菜单创建Unity内部数据表(ScriptableObject)
  • 鸿蒙学习之TypeScript 语法理解笔记
  • LightDB to_char 三入参函数支持
  • 吉祥物虚拟人IP:如何持续为品牌年轻化营销赋能
  • 面试篇:算法(二:二叉树)
  • 信而泰IPSec测试方法
  • 【SpringCloud】Gateway 配置全局过滤器获取请求参数和响应值
  • vs查找与替换功能【在文件中查找】不显示任何结果
  • 【objectarx.net】加载线型文件