Loading [MathJax]/jax/output/CommonHTML/config.js
前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >【优选算法篇】分治策略,速战速决:快速选择排序的神奇之处(下篇)

【优选算法篇】分治策略,速战速决:快速选择排序的神奇之处(下篇)

作者头像
熬夜学编程的小王
发布于 2024-12-24 02:22:22
发布于 2024-12-24 02:22:22
16900
代码可运行
举报
文章被收录于专栏:编程小王编程小王
运行总次数:0
代码可运行

须知

💬 欢迎讨论:如果你在学习过程中有任何问题或想法,欢迎在评论区留言,我们一起交流学习。你的支持是我继续创作的动力! 👍 点赞、收藏与分享:觉得这篇文章对你有帮助吗?别忘了点赞、收藏并分享给更多的小伙伴哦!你们的支持是我不断进步的动力! 🚀 分享给更多人:如果你觉得这篇文章对你有帮助,欢迎分享给更多对C++算法感兴趣的朋友,让我们一起进步!

接上篇: 【优选算法篇】揭秘快速排序:分治算法如何突破性能瓶颈(上篇)-CSDN博客

引言:通过上篇文章带大家简单了解“分治(快速排序)算法”,小试牛刀。接下来将让大家感受一下分治(快速排序)在解题的更多妙处。

1. C++ 分治(快速选择排序)算法详解

1.1 分治法的定义:

分治法是一种将一个大问题分解为多个子问题并解决这些子问题的策略,通常包含三个步骤:

  • 分解(Divide): 将原始问题分解成多个子问题。
  • 解决(Conquer): 递归地解决每个子问题。
  • 合并(Combine): 将子问题的解合并成原始问题的解。

分治法的关键在于能否将问题成功分解,并且保证每个子问题都能被有效解决。

1.2 快速选择排序(Quick Select)算法的核心思想:

快速选择排序(Quick Select)是一种基于快速排序思想的选择算法,它用于找到数组中的第 k 小元素,而不是对数组进行完全排序。它的核心思想如下:

  • 与快速排序类似,选择一个“枢纽”(pivot)元素,通常使用“三数取中法”选择枢纽,以避免最坏情况。
  • 将数组分成两部分:
    • 左边部分包含所有小于枢纽的元素。
    • 右边部分包含所有大于枢纽的元素。
  • 根据第 k 小元素的位置来决定递归的方向:
    • 如果第 k 小元素在左部分,则递归在左部分继续查找。
    • 如果第 k 小元素在右部分,则递归在右部分继续查找。
    • 如果第 k 小元素就是枢纽元素的位置,则直接返回该元素。
1.3 快速选择排序的应用:

快速选择排序的经典应用主要集中在以下几个领域:

  • 寻找第 k 小/大元素: 在实际应用中,快速选择排序广泛用于查找数据集合中的第 k 小或第 k 大的元素,尤其在大数据量的处理下,能够有效减少时间复杂度。
  • 数据分析和统计: 在数据分析中,常常需要查找排名前 k 的数据项,快速选择排序在这些场景中表现出色。
  • 排名算法: 在搜索引擎中,用于排名结果时,快速选择排序可以高效地找出前 k 个最相关的文档。
1.4 快速选择排序的优势和重要性:
  • 时间复杂度: 快速选择排序的平均时间复杂度为 O(n),而最坏情况为 O(n²)(类似于快速排序),但通过三数取中法或随机选择枢纽,可以大大降低最坏情况发生的概率。大多数情况下,快速选择排序的时间复杂度为 O(n),比起需要完全排序的 O(n log n) 快速排序来说要高效得多。
  • 空间复杂度: 快速选择排序是原地排序算法,不需要额外的存储空间,所以它的空间复杂度为 O(1),比其他排序算法(如归并排序)的 O(n) 空间复杂度要好。
  • 经典的分治法应用: 快速选择排序是分治法的经典应用之一,通过选择合适的枢纽,将原问题分解为两个子问题,在不断缩小问题规模的过程中找到第 k 小的元素。
1.5 快速选择排序的核心思想:

快速选择排序的核心思想是在分治法框架下进行快速查找第 k 小元素,步骤包括:

  1. 选择枢纽(Pivot): 选择一个枢纽元素,可以使用三数取中法来避免极端情况。
  2. 分区(Partition): 将数组按照枢纽分成两部分,左边部分小于枢纽,右边部分大于枢纽。
  3. 定位第 k 小元素:
    • 如果枢纽正好位于第 k 小元素的位置,返回枢纽。
    • 如果第 k 小元素在左部分,递归地在左部分查找。
    • 如果第 k 小元素在右部分,递归地在右部分查找。
1.6 快速选择排序的代码示例:
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <iostream>
#include <vector>
#include <algorithm>

// 分区函数
int partition(std::vector<int>& nums, int left, int right) {
    int pivot = nums[right];  // 选择最右边的元素作为枢纽
    int i = left - 1;
    
    for (int j = left; j < right; ++j) {
        if (nums[j] < pivot) {
            i++;
            std::swap(nums[i], nums[j]);
        }
    }
    std::swap(nums[i + 1], nums[right]);
    return i + 1;
}

// 快速选择函数
int quickSelect(std::vector<int>& nums, int left, int right, int k) {
    if (left == right) return nums[left];  // 只有一个元素时直接返回
    
    int pivotIndex = partition(nums, left, right);
    
    if (k == pivotIndex) {
        return nums[k];  // 如果枢纽位置就是第 k 小元素,返回它
    } else if (k < pivotIndex) {
        return quickSelect(nums, left, pivotIndex - 1, k);  // 在左半部分查找
    } else {
        return quickSelect(nums, pivotIndex + 1, right, k);  // 在右半部分查找
    }
}

int main() {
    std::vector<int> nums = {3, 2, 1, 5, 6, 4};
    int k = 2;  // 查找第 2 小的元素
    std::cout << "The " << k << "th smallest element is: " << quickSelect(nums, 0, nums.size() - 1, k - 1) << std::endl;
    return 0;
}
1.7 总结:
  • 快速选择排序利用分治法对数组进行分区,递归地查找第 k 小元素,避免了排序整个数组的高时间复杂度。
  • 它的平均时间复杂度为 O(n),适合用于大规模数据集中的选择问题,尤其是在只需要找到某个特定位置的元素而不是排序整个数组时。
  • 通过灵活选择枢纽元素(如三数取中法或随机选择),可以有效降低最坏情况的发生概率,确保算法的高效性。

2. 题目1:数组中第k个最大元素

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

题目描述:

2.1 算法思路:

核心算法思想

  • 快速排序的核心思想是通过选择一个基准元素(pivot),将数组分为两个部分:一部分小于基准元素,另一部分大于基准元素。在对每一部分继续递归排序后,整个数组被排序好。
  • 快速选择的思想是类似的,但与快速排序不同,快速选择只关心第 k 大的元素,而不需要对整个数组排序。通过在每次分区后缩小查找的范围,最终定位到第 k 大的元素。

算法流程

  1. 随机化: 通过 getRandom() 函数随机选择一个基准元素(pivot),这能够避免最坏情况(即每次选择的基准元素是当前子数组的最大或最小元素,导致退化为 O(n²) 的时间复杂度)。
  2. 三路分区: 使用三路分区算法(Dutch National Flag Algorithm)将数组分为三部分:
    • 小于基准元素的部分。
    • 等于基准元素的部分。
    • 大于基准元素的部分。
  3. 递归选择: 根据第 k 大元素的位置决定下一步递归:
    • 如果第 k 大元素在右边部分,递归到右边部分。
    • 如果第 k 大元素就是基准元素,直接返回基准元素。
    • 如果第 k 大元素在左边部分,递归到左边部分。
  4. 返回结果: 最终找到第 k 大元素时返回。
2.2 代码实现:
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution 
{
public:
    // 主函数,找到数组中的第 k 大元素
    int findKthLargest(vector<int>& nums, int k) 
    {
        srand(time(NULL));  // 使用当前时间初始化随机数生成器,确保每次执行时选择不同的基准元素
        return qsort(nums, 0, nums.size() - 1, k);  // 调用快速选择算法的主函数
    }

    // 快速选择算法的递归实现,返回第 k 大元素
    int qsort(vector<int>& nums, int l, int r, int k)
    {
        if (l == r) return nums[l];  // 如果当前子数组只剩下一个元素,直接返回该元素

        int i = l, left = l - 1, right = r + 1;  // 初始化三个指针:i、left 和 right
        int key = getRandom(nums, l, r);  // 随机选择一个基准元素

        // 三路分区:小于基准、等于基准和大于基准
        while (i < right)
        {
            if (nums[i] < key) 
                swap(nums[++left], nums[i++]);  // 如果 nums[i] 小于基准,移动到左侧
            else if (nums[i] == key) 
                i++;  // 如果 nums[i] 等于基准,跳过当前元素
            else 
                swap(nums[i], nums[--right]);  // 如果 nums[i] 大于基准,移动到右侧
        }

        // 计算基准元素在数组中所占的大小
        int b = right - left - 1;  // 等于基准元素的数量
        int c = r - right + 1;     // 大于基准元素的数量

        // 根据第 k 大元素的位置来决定下一步的递归
        if (c >= k) 
            return qsort(nums, right, r, k);  // 如果第 k 大元素在右侧部分,递归右部分
        else if (b + c >= k) 
            return key;  // 如果第 k 大元素是基准元素,返回基准元素
        else 
            return qsort(nums, l, left, k - b - c);  // 否则,第 k 大元素在左侧部分,递归左部分
    }

    // 随机选择一个基准元素
    int getRandom(vector<int>& nums, int left, int right)
    {
        int n = rand();  // 生成一个随机数
        return nums[n % (right - left + 1) + left];  // 从区间 [left, right] 中随机选择一个元素
    }
};
2.2.1 代码解读
  1. findKthLargest:
    • 接受一个整数数组 nums 和一个整数 k,返回数组中第 k 大的元素。
    • 使用 srand(time(NULL)) 来初始化随机数种子,确保每次运行时随机数不同。
    • 调用 qsort 函数来执行快速选择算法,查找第 k 大元素。
  2. qsort (快速选择算法):
    • 接受参数:nums(数组),l(子数组的左边界),r(子数组的右边界),k(第 k 大的元素)。
    • if (l == r):如果子数组只包含一个元素,直接返回该元素。
    • 随机选择一个基准元素 key,并使用三路分区法(类似于快速排序)将数组分为三个部分:小于基准、大于基准和等于基准。
    • 根据分区结果,递归地选择下一部分来查找第 k 大的元素。
  3. 三路分区法:
    • leftright 分别指向小于基准和大于基准的元素的边界,i 用来遍历数组。
    • 如果 nums[i] < key,将 nums[i] 移到小于基准的部分。
    • 如果 nums[i] == key,保持该元素位置不动,继续扫描。
    • 如果 nums[i] > key,将 nums[i] 移到大于基准的部分。
  4. 递归逻辑:
    • 根据分区后的情况判断第 k 大元素的位置:
      • 如果第 k 大元素在右侧(大于基准的部分),递归右部分。
      • 如果第 k 大元素正好是基准元素,返回基准元素。
      • 如果第 k 大元素在左侧(小于基准的部分),递归左部分。
  5. getRandom:
    • 用于从 [left, right] 范围内随机选择一个元素作为基准。通过 rand() 生成一个随机数,并利用模运算确保结果在给定区间内。
2.3 多种解法
2.3.1 解法2: 堆(Heap)

使用堆(通常是最小堆)可以有效地找到数组中的第 K 大元素。通过构建一个大小为 K 的最小堆,堆中的最小元素将始终是第 K 大元素。

算法思路:

  • 创建一个最小堆,堆的大小为 K。
  • 遍历数组,对于每个元素:
    • 如果堆中有不到 K 个元素,则直接加入堆。
    • 如果堆已满且当前元素大于堆顶元素,则替换堆顶元素。
  • 最终,堆顶元素就是第 K 大元素。

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minHeap;  // 创建一个最小堆
        for (int num : nums) {
            minHeap.push(num);
            if (minHeap.size() > k) {
                minHeap.pop();  // 维持堆的大小为 k
            }
        }
        return minHeap.top();  // 堆顶元素即为第 k 大元素
    }
};

时间复杂度:

  • 插入每个元素的时间复杂度是 O(log k),因此整个过程的时间复杂度为 O(n log k)。
2.3.2 解法3:排序法

最直接的解法是将数组排序,然后返回排序后数组的第 K 个元素。由于排序的时间复杂度为 O(n log n),这虽然简单,但在效率上不如快速选择和堆。

算法思路:

  • 对数组进行排序,返回数组中倒数第 K 个元素。

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end(), greater<int>());
        return nums[k - 1];  // 排序后返回第 K 个元素
    }
};

时间复杂度:

  • 排序的时间复杂度为 O(n log n)。
2.3.3 解法4:快排(快速排序)

快速排序可以修改为只排序部分数组,达到在 O(n log n) 时间内找到第 K 大元素。通过每次递归仅对部分数组进行排序来优化。

算法思路:

  • 对数组进行快速排序,只排序包含第 K 大元素的部分。

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        quickSort(nums, 0, nums.size() - 1, k);
        return nums[k - 1];
    }

    void quickSort(vector<int>& nums, int left, int right, int k) {
        if (left < right) {
            int pivotIndex = partition(nums, left, right);
            if (pivotIndex == k - 1) return;
            else if (pivotIndex < k - 1) quickSort(nums, pivotIndex + 1, right, k);
            else quickSort(nums, left, pivotIndex - 1, k);
        }
    }

    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[right];
        int i = left;
        for (int j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                swap(nums[i], nums[j]);
                i++;
            }
        }
        swap(nums[i], nums[right]);
        return i;
    }
};

时间复杂度:

  • 最坏情况下时间复杂度为 O(n^2),但平均情况下是 O(n log n)。
2.3.4 解法5:计数排序法(桶排序)

如果数组中的元素范围比较小,可以使用计数排序来找出第 K 大元素。计数排序在元素范围已知且较小的情况下非常高效。

算法思路:

  • 统计每个元素出现的次数,然后从最大元素开始统计,直到找到第 K 大的元素。

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int maxNum = *max_element(nums.begin(), nums.end());
        vector<int> count(maxNum + 1, 0);
        
        // 统计每个数字的出现频率
        for (int num : nums) {
            count[num]++;
        }

        // 从最大值开始查找第 K 大元素
        for (int i = maxNum; i >= 0; i--) {
            if (count[i] > 0) {
                k -= count[i];
                if (k <= 0) return i;
            }
        }
        return -1;  // 默认情况不应到达
    }
};

时间复杂度:

  • 计数排序的时间复杂度为 O(n + m),其中 n 是数组的大小,m 是元素的范围。
2.3.5 总结
  • 快速选择算法(Quick Select):时间复杂度为 O(n)(平均情况),适用于大多数情况,避免了不必要的排序。
  • 堆排序法(Heap):时间复杂度为 O(n log k),适合 K 较小的情况。
  • 排序法:时间复杂度为 O(n log n),简单易懂,但效率较低。
  • 快速排序:O(n log n),但可以通过调整递归范围来优化。
  • 计数排序法:适用于元素范围较小的情况,时间复杂度为 O(n + m)。
2.4 算法的时间复杂度
  • 平均时间复杂度: 在平均情况下,快速选择算法的时间复杂度为 O(n),因为每次分区后,问题规模大约减半。
  • 最坏时间复杂度: 在最坏情况下(每次选择的基准元素都是最小或最大的元素),时间复杂度退化为 O(n²)。但是,随机选择基准元素大大减少了最坏情况发生的概率。
  • 空间复杂度: 快速选择算法的空间复杂度是 O(1),因为它是原地操作,不需要额外的存储空间。
2.5 总结

该算法实现了 快速选择(Quick Select)算法来查找数组中的第 k 大元素,使用了随机化和三路分区的策略来提高效率。通过随机选择基准元素,避免了最坏情况的发生,通常在平均情况下,算法的时间复杂度为 O(n),比直接排序(O(n log n))更高效。

3. 题目2:面试题 17.14. 最小k个数

题目链接:面试题 17.14. 最小K个数 - 力扣(LeetCode)

题目描述:

3.1 算法思路:

  1. 随机化快速选择(Quick Select):
    • 快速选择算法通过选择一个随机基准(pivot),然后将数组分为三部分:
      1. 小于基准的部分
      2. 等于基准的部分
      3. 大于基准的部分
    • 通过递归选择包含第 K 个最小元素的那部分来找到前 K 小的元素。
  2. 核心操作:
    • qsort 是一个递归函数,其目标是根据基准值将数组分为两部分,最终将最小的 K 个元素放到数组的前 K 个位置。
    • 选择一个随机的基准元素,然后通过三路划分(Three-way partition)将数组分为三部分。
    • 递归的调整左右边界,直到得到前 K 个最小的元素。
3.2 代码实现:
代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution 
{
public:
    vector<int> smallestK(vector<int>& arr, int k) 
    {
        srand(time(NULL));  // 初始化随机数种子
        qsort(arr, 0, arr.size()-1, k);  // 调用快速选择函数

        return {arr.begin(), arr.begin() + k};  // 返回数组中最小的 K 个元素
    }

    void qsort(vector<int>& arr, int l, int r, int k)
    {
        if(l >= r) return;  // 如果区间内只有一个元素,结束递归

        int left = l - 1, right = r + 1, i = l;
        int key = getRandom(arr, l, r);  // 随机选择一个基准元素
        while(i < right)
        {
            if(arr[i] < key) 
                swap(arr[++left], arr[i++]);  // 将小于基准的元素移到左边
            else if(arr[i] == key) 
                i++;  // 如果等于基准元素,直接跳过
            else 
                swap(arr[--right], arr[i]);  // 将大于基准的元素移到右边
        }

        int a = left - l + 1, b = right - left - 1;

        if(a > k) 
            qsort(arr, l, left, k);  // 如果前 a 个元素已经包含了 K 个最小的元素,递归左半部分
        else if(a + b >= k) 
            return;  // 如果已经找到前 K 个最小的元素,结束
        else 
            qsort(arr, right, r, k - a - b);  // 否则递归右半部分
    }

    int getRandom(vector<int>& arr, int left, int right)
    {
        return arr[rand() % (right - left + 1) + left];  // 随机选择一个基准元素
    }
};
3.2.1 核心步骤解析:
  1. smallestK 函数:
    • 输入:arr(整数数组),k(需要找到最小的 K 个元素)。
    • 调用 qsort 进行快速选择,递归地确定前 K 个最小的元素,并且返回前 K 个元素作为结果。
  2. qsort 函数:
    • 这是一个递归函数,通过快速选择算法实现。
    • 三路划分:通过随机选择一个基准元素,将数组分为三个部分:
      • 小于基准的部分
      • 等于基准的部分
      • 大于基准的部分
    • 递归地处理包含最小 K 个元素的部分,直到找到第 K 小元素。
  3. getRandom 函数:
    • 用于从数组的子区间中随机选择一个元素作为基准。
    • rand() % (right - left + 1) + left 是一个经典的随机选择区间元素的方法。

递归分治过程:

  • 假设我们每次选择一个基准元素,然后将数组分成了小于基准、等于基准和大于基准的三部分:
    • a:表示小于基准的元素数量。
    • b:表示等于基准的元素数量。
  • 如果 a >= k,意味着最小的 K 个元素都在基准左边,因此递归处理左边部分。
  • 如果 a + b >= k,说明当前基准元素是第 K 小的元素,直接返回,不需要再递归。
  • 如果 a + b < k,递归处理右边部分,寻找剩余的第 k - a - b 小的元素。
3.3 多种解法
3.3.1 解法 2:排序法

最直观的方法是对数组进行排序,然后返回前 k 个元素。

步骤:

  1. 对数组 arr 进行升序排序。
  2. 返回排序后的前 k 个元素。

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        sort(arr.begin(), arr.end());  // 对数组进行升序排序
        return vector<int>(arr.begin(), arr.begin() + k);  // 返回前 k 个元素
    }
};

时间复杂度:

  • 排序的时间复杂度是 O(nlogn),其中 n 是数组的长度。
  • 返回前 k 个元素的时间复杂度是 O(k),但通常可以认为 O(k)O(nlogn) 要小,因此总时间复杂度是 O(nlogn)

空间复杂度:

  • 使用了 O(n) 的额外空间来存储排序后的数组。

3.3.2 解法 3:最小堆(优先队列)

使用最小堆来维护当前数组中最小的 k 个元素。可以通过构建一个大小为 k 的最小堆来解决。

步骤:

  1. 使用一个大小为 k 的最小堆(或者最大堆,下面我们将使用最大堆)。
  2. 遍历数组的每个元素:
    • 如果堆的大小小于 k,则直接将当前元素加入堆中。
    • 如果堆的大小已经达到 k,则与堆顶元素比较,如果当前元素更小,则弹出堆顶元素,并将当前元素加入堆中。
  3. 最终堆中存储的就是最小的 k 个元素。

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <queue>

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        priority_queue<int> maxHeap;  // 最大堆
        for (int num : arr) {
            if (maxHeap.size() < k) {
                maxHeap.push(num);  // 堆的大小小于 k,直接加入
            } else if (num < maxHeap.top()) {
                maxHeap.pop();  // 弹出堆顶元素
                maxHeap.push(num);  // 加入当前元素
            }
        }

        vector<int> result;
        while (!maxHeap.empty()) {
            result.push_back(maxHeap.top());
            maxHeap.pop();
        }
        reverse(result.begin(), result.end());  // 由于是最大堆,最后要反转结果
        return result;
    }
};

时间复杂度:

  • 对于每个元素的操作(插入堆或删除堆顶元素)需要 O(log k) 时间。
  • 遍历整个数组需要 O(n) 次操作。
  • 因此,总时间复杂度为 O(n log k)

空间复杂度:

  • 使用一个大小为 k 的堆,空间复杂度为 O(k)

3.3.3 解法4: 使用排序并维护最小 k 个元素

这是一种通过逐步维护前 k 个元素的方法。可以使用 std::partial_sort 来高效地获取数组的前 k 个最小元素。

步骤:

  1. 使用 std::partial_sort 对数组进行排序,只将前 k 个元素排序,而不对整个数组进行排序。
  2. 返回前 k 个元素。

代码实现:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <algorithm>

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        partial_sort(arr.begin(), arr.begin() + k, arr.end());
        return vector<int>(arr.begin(), arr.begin() + k);
    }
};

时间复杂度

  • std::partial_sort 的时间复杂度是 O(n log k)

空间复杂度

  • 空间复杂度为 O(n),主要是由于排序时可能需要额外的空间。
3.3.4 总结:
3.4 时间复杂度:
  • 平均情况下,快速选择的时间复杂度为 O(n),因为它通过递归缩小问题规模,每次将数组分成两部分,平均每次会处理约一半的元素。
  • 最坏情况下,时间复杂度为 O(n^2),但通过随机选择基准元素可以避免最坏情况,因此大多数情况下是 O(n)。

优点:

  • 效率高:由于快速选择算法的平均时间复杂度为 O(n),该方法在实际应用中通常表现很好,尤其是当 k 比较小或者数组很大的时候。
  • 避免了不必要的排序:与全排序(时间复杂度 O(n log n))相比,快速选择通过分治策略避免了对整个数组的排序,只聚焦于最小的 K 个元素,节省了计算时间。

缺点:

  • 最坏情况较差:虽然通过随机化可以减少最坏情况的出现,但最坏情况的时间复杂度仍然是 O(n^2),需要注意。
3.5 总结:

这段代码通过 快速选择算法 来有效地找到数组中最小的 K 个元素。算法利用随机化技术避免了最坏情况,并通过分治策略将时间复杂度保持在 O(n)(平均情况下),非常适合大规模数据的处理。

4.总结

我们发现,排序法适用于简单场景,最小堆适合 K 较小的数据集,快速选择算法在大数据量下效率最高,部分排序法则能够快速得到前 K 个元素,尤其适用于空间敏感和实时计算的场景。

在处理数组元素的选择问题时,选择合适的算法不仅能提高效率,也能在大数据和高性能计算需求中展现出明显优势,特别是在 时间复杂度敏感数据量较大的 应用中。

5.最后

通过上面几个例题:「最小的 K 个数字」的多种解法「快速选择算法」的应用最小堆排序、以及排序法,我们总结出高效解决数组中最小 K 个元素问题的几种常见策略。 排序法最小堆快速选择算法部分排序法在数组问题中有着广泛的应用。它们的本质是在数组中寻找前 K 个元素,虽然方法不同,但都具有显著的时间复杂度优化特性。

  • 排序法通过将数组完全排序,然后截取前 K 个元素,简单易懂,但其时间复杂度较高,适用于元素数量不大或要求实现简单的场景。
  • 最小堆方法通过构建堆来维护前 K 个最小的元素,它的优势在于时间复杂度为 O(n log k),特别适合大规模数据且 K 较小的情况,常用于实时数据处理。
  • 快速选择算法通过分治法(与快速排序类似)定位第 K 小的元素,平均时间复杂度为 O(n),其空间复杂度较低,适用于处理大数据集时提高效率,特别适用于要求时间效率高且能够容忍最坏情况的应用。
  • 部分排序法使用 partial_sort 来进行部分排序,只排序前 K 个元素,时间复杂度为 O(n log k),它能够在不完全排序的情况下快速获得结果,适合对部分元素有要求的场景。

路虽远,行则将至;事虽难,做则必成

亲爱的读者们,下一篇文章再会!!!

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2024-12-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
【分治】数组中的第K个最大元素(快速选择算法)
​ 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
利刃大大
2025/05/21
1000
【分治】数组中的第K个最大元素(快速选择算法)
【优选算法篇】化繁为简,见素抱朴:从乱象中重构秩序的艺术
给定一个包含红色、白色和蓝色的数组 nums,共 n 个元素,要求对它们进行原地排序,使得相同颜色的元素相邻,并按红色、白色、蓝色的顺序排列。这里使用整数 0、1 和 2 分别表示红色、白色和蓝色,且不能使用库的排序函数。
半截诗
2024/11/21
860
【优选算法篇】化繁为简,见素抱朴:从乱象中重构秩序的艺术
算法专题六: 模拟与分治快排
算法思路: 本题就是简单的模拟, 只需按照题目的思路遍历所有的字符, 如果为?则将其替换, 替换时寻找26个小写字母中符合要求的, 即前一个字符和后一个字符都不等于当前字符, 如果为第一个字符和最后一个字符就不需要判断.
用户11317877
2024/10/16
1010
算法专题六: 模拟与分治快排
深度解析之算法之分治(快排)
题目链接 给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地 对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
Undoom
2025/04/26
840
深度解析之算法之分治(快排)
快速选择算法Golang实现
类似求TopK问题中最常用的算法中,从时间复杂度最高到中等再到最优分别有不同的做法。在之前的学习中只学到了使用堆来优化TopK问题,但是这样的时间复杂度只能做到O(Nlogk)的大小,其中k是堆的大小。有一种更好的办法是基于快速排序的思想去优化的算法,叫做快速选择算法,它的时间复杂度能够做到O(N)的时间复杂度。这里的思路是:每次通过随机取得一个分区键,假设题目要求数组按照从大到小排序,那么通过将分区键移动到头部start,然后从头部的下一个元素开始遍历数组,遇到比分区键大的元素就交换到分区键后的已排序的下标的下一个位置,该指针假设就叫做index。最后遍历结束后将index的值与start的值交换,此时分区键就被移动到了index指针所指的位置,那么index左边的元素都是比分区键要大的,此时再通过对比index - start 与k的大小关系就可以判断下一次递归要从哪个区间开始,从而减少遍历的次数。
dddyge
2022/11/20
4760
初识算法 · 分治(2)
​本文的主题是分治,通过两道题目讲解,一道是数组中的第k个最大元素,一道是最小的k个数。 链接分别为: 215. 数组中的第K个最大元素 - 力扣(LeetCode)
_lazy
2024/11/26
1080
初识算法 · 分治(2)
【优选算法】D&C-Quicksort-Mysteries:分治-快排的算法之迷
本篇是优选算法之分治-快排,快排可以在更短的时间内完成相同规模数据的排序任务,大大提升了运算效率,空间复杂度在平均状况下仅为O(log N)
DARLING Zero two
2025/01/20
880
【优选算法】D&C-Quicksort-Mysteries:分治-快排的算法之迷
【优选算法篇】揭秘快速排序:分治算法如何突破性能瓶颈(上篇)
分治法是一种非常高效的算法设计策略,广泛应用于计算机科学的多个领域,尤其是在解决复杂问题时,它通过将大问题拆解成更小的子问题来降低问题的复杂度。快速排序(QuickSort)是分治法中的经典例子,能够在许多实际场景中提升性能。它的重要性体现在以下几个方面:
熬夜学编程的小王
2024/12/24
1130
【优选算法篇】揭秘快速排序:分治算法如何突破性能瓶颈(上篇)
【数据结构与算法】:选择排序与快速排序
在这里我们可以遍历一次同时找到最小元素和最大元素,对应放到相应的位置, 基本代码如下:
用户11029103
2024/03/19
4220
【数据结构与算法】:选择排序与快速排序
算法训练之分治(快速排序)
在正式开始运用分治算法之前,我们首先来看看颜色分类的问题,方便我们后面的学习~
用户11352420
2025/05/21
840
算法训练之分治(快速排序)
【分治】最小的k个数
输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。
利刃大大
2025/05/22
600
【分治】最小的k个数
【LeetCode 热题 100】215. 数组中的第K个最大元素(Python 快速选择详解)
在刷 LeetCode 的过程中,“第K大”是一个非常高频的考点,而题目 215. 数组中的第K个最大元素 就是经典代表。这道题不仅考察我们对排序的理解,还挑战我们写出时间复杂度为 O(n) 的算法。
未名编程
2025/05/11
850
Lucene系列(14)工具类之快速选择算法
计算集合中第 k 大(小)的元素。就是 topK 相关系列的问题,但是选择算法只需要找到第 k 个就好。
呼延十
2021/03/29
7250
Lucene系列(14)工具类之快速选择算法
【快排算法】颜色分类 / 排序数组 / 数组中的第K个最大元素 / LCR 库存管理 III
快速选择算法是用于在无序数组中寻找第 k 小(或第 k 大)元素的高效算法 ,是快速排序算法的一个变种。
_小羊_
2025/04/09
620
【快排算法】颜色分类 / 排序数组 / 数组中的第K个最大元素 / LCR 库存管理 III
文心一言 VS 讯飞星火 VS chatgpt (99)-- 算法导论9.3 5题
为了在线性时间内解决任意顺序统计量的选择问题,我们可以使用一个基于快速选择算法的方法。快速选择算法是基于快速排序的思想,可以在平均情况下以线性时间复杂度找到第k小的元素。
福大大架构师每日一题
2023/09/25
2120
文心一言 VS 讯飞星火 VS chatgpt (99)-- 算法导论9.3 5题
【算法专题】分治 - 快速排序
题目:给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。 必须在不使用库内置的 sort 函数的情况下解决这个问题。
YoungMLet
2024/03/01
1230
算法思想总结:分治思想
1,快速排序本身相当于一个前序遍历,最好的时间复杂度是NlogN 最差的时间复杂度是N^2 ,最坏的情况是出现在(1)以最左侧或最右侧为基准值的时候,凑巧又接近有序(2)大量重复元素。为了解决这个问题衍生出了优化思路:三组划分+随机取key。并且这种方式还可以解决top-k问题,并且时间复杂度是o(N)比堆排序还优秀,我们称之为快速选择算法。
小陈在拼命
2024/04/14
1650
算法思想总结:分治思想
万字长文|十大基本排序,一次搞定!
大家好,我是老三,一个刷不动算法的程序员。排序算法相关题目尽管在力扣中不是很多,但是面试中动不动要手撕一下。接下来,我们看一下十大基本排序,
三分恶
2021/09/08
5530
①归并排序、快速排序 、堆排序、计数排序[算法、代码模板、面试题]
个人简介:Java领域新星创作者;阿里云技术博主、星级博主、专家博主;正在Java学习的路上摸爬滚打,记录学习的过程~ 个人主页:.29.的博客 学习社区:进去逛一逛~
.29.
2023/12/06
4610
①归并排序、快速排序 、堆排序、计数排序[算法、代码模板、面试题]
【算法】TopK问题超详解
比如大众点评的必吃榜;成绩单的前十名;各种数据的最值筛选; [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NOc0UsTc-1721352065061)(https://i-blog.csdnimg.cn/direct/d54a704560c64ea0991b938683e70d1e.png)]
Skrrapper
2024/08/05
1840
推荐阅读
相关推荐
【分治】数组中的第K个最大元素(快速选择算法)
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验