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

【分支-快速排序】

article 2024/11/18 12:34:46

【分支-快速排序】

  • 1. 颜色分类
    • 1.1 题目来源
    • 1.2 题目描述
    • 1.3 题目解析
  • 2. 排序数组
    • 2.1 题目来源
    • 2.2 题目描述
    • 2.3 题目解析
  • 3. 数组中的第K个最大元素
    • 3.1 题目来源
    • 3.2 题目描述
    • 3.3 题目解析
  • 4. 库存管理 III
    • 4.1 题目来源
    • 4.2 题目描述
    • 4 .3 题目解析

1. 颜色分类

1.1 题目来源

75. 颜色分类

1.2 题目描述

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

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

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

  1. 示例 1：
    输入：nums = [2,0,2,1,1,0]
    输出：[0,0,1,1,2,2]
  2. 示例 2：
    输入：nums = [2,0,1]
    输出：[0,1,2]

提示：
n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

1.3 题目解析

方法一：使用快速排序

这里就是简单的一个快排模板了.

class Solution {
public:
    void QuickSortHoare(vector<int>& a, int left, int right)
    {
        if (left >= right)
            return;

        int l = left, r = right;
        int key = left;

        while (l < r)
        {
            while (l < r && a[r] >= a[key]) // 这里要注意了一定要写等号,也必须是r先--在l++
                r--;
            while (l < r && a[l] <= a[key])
                l++;
            swap(a[l], a[r]);
        }
        swap(a[left], a[l]);
        QuickSortHoare(a, left, l - 1);
        QuickSortHoare(a, l + 1, right);
    }
    void sortColors(vector<int>& nums) 
    {
        QuickSortHoare(nums, 0, nums.size() - 1);
    }
};

方法二：三指针

我们可以将整个数组分成三部分呢，第一部分全部是0，第二部分全部都是1，第三部分全部都是2。于是我们可以定义三个指针，left，cur，right，left代表第一部分的最右边，right代表第三部分的最左边，cur指针用于遍历整个数组。这样的话我们就可以得到一个范围，即[left,l]为第一部分，[l + 1, r - 1]是第二部分，[r, right]是第三部分。

这里的解题思路可以参考移动零。

所以我们就可以得到三个部分：

  1. 如果nums[cur] == 0 ，就swap（nums[cur], nums[left + 1]，同时将left和cur都进行++
  2. 如果nums[cur] == 1，则cur直接进行++
  3. 如果num[cur] == 2，则swap(nums[cur], nums[right - 1])，同时right进行–，这个时候cur不需要进行++，因为right - 1下标对应的数据是还没有进行判断的，有可能是0，有可能是1，也有可能是2，是不确定的，所以还需要进行判断。
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int left = -1 , right = n;
        int cur = 0;
        
        while (cur < right)
        {
            if (nums[cur] == 0)
            {
                swap(nums[left + 1], nums[cur]);
                left++;
                cur++;
            }
            else if (nums[cur] == 1)
            {
                cur++;
            }
            else
            {
                swap(nums[right - 1],nums[cur]);
                right--;
            }
        }
    }
};

2. 排序数组

2.1 题目来源

912. 排序数组

2.2 题目描述

给你一个整数数组 nums，请你将该数组升序排列。

  1. 示例 1：
    输入：nums = [5,2,3,1]
    输出：[1,2,3,5]
  2. 示例 2：
    输入：nums = [5,1,1,2,0,0]
    输出：[0,0,1,1,2,5]

提示：
1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

2.3 题目解析

方法一：快排模板

直接使用快排模板，这里需要注意了int key = a[(left + right) >> 1];必须写成key直接拿到值，不能使用通过拿到下标的方式int key = (left + right) >> 1，然后后序使用while (a[r] > a[key])这样通过索引的方式进行判断，因为可能在整个whiel(l < r）的阶段中key所对应下标的值会发生改变。只有一开始拿到索引对应的值后继续使用方可。

class Solution {
public:
    void _sort(vector<int>& a, int left, int right)
    {
        if (left >= right) return;
        
        int l = left, r = right;
        int key = a[(left + right) >> 1];
        while (l <= r)
        {
            while (a[r] > key)
                r--;
            while (a[l] <key)
                l++;
            if (l <= r)
            {
                swap(a[l], a[r]);
                l++;
                r--;
            }
        }
        _sort(a, left, r);
        _sort(a, l, right);
    }
    vector<int> sortArray(vector<int>& nums) {
        _sort(nums, 0, nums.size() - 1);
        return nums;
    }
};

方法二：使用三指针+随机取key值

向上面那样如果直接使用快排的模板的话，如果是全部都是相同的数，或者这个数组本身就是一个有序的话，那么直接使用快排模板的话时间复杂度将会达到O(N^2)所以我们可以对快排进行优化。同样的我们也可以划分为三部分，第一部分是小于key（基准值）的，第二部分是等于key的，第三部分是大于key的。于是我们可以定义三个指针，left，cur，right，left代表第一部分的最右边，right代表第三部分的最左边，cur指针用于遍历整个数组。这样我们递归只需要对范围为[left, l]和[r, right]范围之间进行递归了。[l+ 1, r - 1]这个区间的范围是不用在进行递归了。而至于key的选取的话，我们之前都是采用第一个或者最后一个或者中间为基准值，这里我们使用使用随机选取的方式。

于是我们就可以得出这样的结论：

  1. 如果nums[cur] < key，则执行swap(nums[left + 1], nums[cur])，同时对left和cur进行++
  2. 如果nums[cur] == key，则只需要对cur进行++即可。
  3. 如果nums[cur] > key，则执行swap(nums[right - 1], nums[cur])，同时只需要对right–即可，cur不需要进行操作，因为被交换过去的nums[right - 1]是还没进行处理的，所以还需要进一步处理。

所以上述这个优化可以将时间复杂度优化接近到NlogN的时间复杂度。

class Solution {
public:
    void _sort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;

        int l = left - 1, r = right + 1; // 这样处理可以提高代码复用度
        int key = nums[rand() % (right - left + 1) + left];
        int cur = left;
        while (cur < r)
        {
            if (nums[cur] < key)
            {
                swap(nums[l + 1], nums[cur]);
                l++;
                cur++;
            }
            else if(nums[cur] == key)
            {
                cur++;
            }
            else
            {
                swap(nums[r - 1], nums[cur]);
                r--;
            }
        }
        _sort(nums, left, l);
        _sort(nums, r, right);
    }
    vector<int> sortArray(vector<int>& nums) {
        _sort(nums, 0, nums.size() - 1);
        return nums;
    }
};

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

3.1 题目来源

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

3.2 题目描述

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

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

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

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

提示：
1 <= k <= nums.length <= 105
-104 <= nums[i] <= 104

3.3 题目解析

方法一：使用快排模板：

class Solution {
public:
    void _sort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;
        int l = left, r = right;
        int key = nums[(left + right) >> 1];
        while (l <= r)
        {
            while (nums[r] > key)
                r--;
            while (nums[l] < key)
                l++;
            if (l <= r)
            {
                swap(nums[l], nums[r]);
                l++;
                r--;
            }
        }
        _sort(nums, left, r);
        _sort(nums, l, right);
    }
    int findKthLargest(vector<int>& nums, int k) 
    {
        _sort(nums, 0, nums.size() - 1);
        return nums[nums.size() - k];
    }
};

方法二：使用三指针数据分三块+随机选取基准值

这里其实和上面几题是一样的方法，也是将数组分成三份，第一部分小于key，第二部分等于key，第三部分大于key。使用三个指针来操作，left，cur，right。left代表第一部分的最右边，right代表第三部分的最左边，cur指针用于遍历整个数组。我们假设第一部分也就是[left, l]的长度是a，第二部分也就是[l + 1, r - 1]的长度是b，第三部分也就是[r， right]的长度是c。现在我们要找到第k大的元素。所以就有一下结论

在这里插入图片描述
所以我们可以得出一下结论：

  1. 如果c >= k，则直接在[r, right]中查找就可以了
  2. 如果 c + b >= k，则直接就是返回[l + 1, r - 1] 中的任意一个值就行。
  3. 如果上述1和2都不满足则需要在[left, l]中进行查找，而这个时候要查找的因该是第(k- b - c）大的数了。
class Solution {
public:
    int _sort(vector<int>& nums, int left, int right, int k)
    {
        int l = left - 1, r = right + 1;
        int key = nums[rand()%(right - left + 1) + left];
        int cur = left;
        while (cur < r)
        {
            if(nums[cur] < key)
            {
                swap(nums[l + 1], nums[cur]);
                l++;
                cur++;
            }
            else if (nums[cur] == key)
            {
                cur++;
            }
            else
            {
                swap(nums[r - 1], nums[cur]);
                r--;
            }
        }
        if (right - r + 1 >= k)
        {
            return _sort(nums, r, right, k);
        }
        else if (right - l >= k)
        {
            return nums[l + 1];
        }
        else
        {
            int c = right - r + 1;
            int b = r - l - 1;
            return _sort(nums, left, l, k - b - c);
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        return _sort(nums, 0, nums.size() - 1, k);
    }
};

4. 库存管理 III

4.1 题目来源

159. 库存管理 III

4.2 题目描述

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

  1. 示例 1：
    输入：stock = [2,5,7,4], cnt = 1
    输出：[2]
  2. 示例 2：
    输入：stock = [0,2,3,6], cnt = 2
    输出：[0,2] 或 [2,0]

提示：
0 <= cnt <= stock.length <= 10000
0 <= stock[i] <= 10000

4 .3 题目解析

这题其实也是使用一样的方法，使用三指针数据分三块+随机选取基准值。

class Solution {
public:
    void _sort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;
        int l = left - 1, r = right + 1;
        int key = nums[rand() % (right - left + 1) + left];
        int cur = left;
        while (cur < r)
        {
            if (nums[cur] < key)
            {
                swap(nums[l + 1], nums[cur]);
                l++;
                cur++;
            }
            else if (nums[cur] == key)
            {
                cur++;
            }
            else
            {
                swap(nums[r - 1], nums[cur]);
                r--;
            }
        }
        _sort(nums, left, l);
        _sort(nums, r, right);
    }
    vector<int> inventoryManagement(vector<int>& stock, int cnt) 
    {
        vector<int> v;
        if (cnt == 0) return v;
        _sort(stock, 0, stock.size() - 1);
        for (int i = 0; i < cnt; i++)
        {
            v.push_back(stock[i]);
        }
        return v;
    }
};

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

相关文章：

  • 麒麟V10，arm64，离线安装docker和docker-compose
  • 使用视频提升应用在 App Store 中的推广效果
  • 【弱监督视频异常检测】2024-ESWA-基于扩散的弱监督视频异常检测常态预训练
  • GitLab 如何降级？
  • Python 打包教程：从零开始构建可分发的Python包
  • 十堰市数据治理：大数据治理在智慧城市中的应用探索
  • Python中如何实现列表的排序
  • 十、组合模式
  • AcWing119 袭击
  • 韩语中的多义词 (치다)柯桥学韩语到蓝天广场附近
  • Python的学习（三十二）---- ctypes库的使用整理
  • LSP协议：打造流动性管理的市场新标杆
  • [前端][js]获取当前正在执行的Javascript脚本文件的路径
  • 项目实现：云备份(一)
  • 【数字集成电路与系统设计】一些Chisel语法的介绍
  • 二、Maven工程的创建--JavaSEJavaEE
  • Element UI按钮组件：构建响应式用户界面的秘诀
  • vue3 ref
  • ffmpeg7.0 AVFrame的分配与释放
  • 使用 DBeaver 创建 MySQL 数据库
  • 第十五届蓝桥杯图形化省赛题目及解析
  • 前端 PDF 预览技巧：标签 vs 插件，如何优雅地展示 PDF 文件
  • 6、多线程
  • 如何使用python运行Flask开发框架并实现无公网IP远程访问
  • 力扣刷题之2555.两个线段获得的最多奖品
  • 装杯 之 Linux 指令1