Hoshiᅟᅠ     

Hoshiᅟᅠ     

关注
发信
关注(28)粉丝(399)

【优选算法篇】化繁为简，见素抱朴：从乱象中重构秩序的艺术

分治专题（一）：快速排序核心思想与应用

前言

第一章：快速排序的应用与延展

1.1 颜色分类（medium）

题目链接：75. 颜色分类

题目描述：

给定一个包含红色、白色和蓝色的数组 nums，共 n 个元素，要求对它们进行原地排序，使得相同颜色的元素相邻，并按红色、白色、蓝色的顺序排列。这里使用整数 0、1 和 2 分别表示红色、白色和蓝色，且不能使用库的排序函数。

示例 1：

  • 输入：nums = [2,0,2,1,1,0]
  • 输出：[0,0,1,1,2,2]
解法（分治思想 - 三指针法实现三分）

算法思路：

颜色分类问题可以视为一种简化的排序问题。我们可以通过“分治”思想，将数组分为三块，分别存储 0、1 和 2，实现“快速”分类。这种方法可以类比于快速排序的分区思想，使用三个指针高效地将数组分成三部分。

  1. 指针定义：

    • left：用于标记 0 序列的末尾位置，初始为 -1。
    • cur：当前扫描位置，初始为 0。
    • right：用于标记 2 序列的起始位置，初始为 n（数组长度）。

  2. 区域划分：

    • [0, left]：全部为 0。
    • [left + 1, cur - 1]：全部为 1。
    • [cur, right - 1]：待定元素。
    • [right, n - 1]：全部为 2。

  3. 扫描与分区：

    • 当 cur < right 时，根据 nums[cur] 的值执行不同操作：
      • 若 nums[cur] == 0：将 cur 位置的 0 与 left + 1 位置的元素交换，并将 left 和 cur 均右移一位。
      • 若 nums[cur] == 1：当前元素 1 已在正确位置，无需交换，直接将 cur 右移。
      • 若 nums[cur] == 2：将 cur 位置的 2 与 right - 1 位置的元素交换，将 right 左移一位，但保持 cur 不变（因为交换过来的元素需要重新判断）。

  4. 循环终止：

    • 当 cur 遇到 right 时，整个数组已被正确分类。最终得到 [0, left] 为 0，[left + 1, right - 1] 为 1，[right, n - 1] 为 2。
C++ 代码实现
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int left = -1, right = n, cur = 0;
        while (cur < right) {
            if (nums[cur] == 0) {
                swap(nums[++left], nums[cur++]); // 将当前 0 移到 0 区间末尾
            } else if (nums[cur] == 1) {
                cur++; // 当前为 1，位置已正确，直接跳过
            } else {
                swap(nums[--right], nums[cur]); // 将当前 2 移到 2 区间起始位置
            }
        }
    }
};
易错点提示

  1. 区间含义理解：

    • left 表示 0 序列的末尾，cur 表示当前扫描位置，right 表示 2 序列的起始位置。在移动指针时，要确保每个区间内的元素始终符合定义。

  2. 保持 cur 不变：

    • 当 nums[cur] == 2 时，交换后需要重新判断 cur 位置，因为此位置交换过来的元素还未被处理。

  3. 确保原地修改：

    • 本题要求在原数组上进行分类，避免额外的空间消耗，因此所有操作都在 nums 数组内完成，符合分治的原地修改原则。
时间复杂度和空间复杂度
  • 时间复杂度：O(n)，cur 指针遍历数组一次，每个元素仅被处理一次。
  • 空间复杂度：O(1)，使用常数个指针进行排序，无额外空间开销。

1.2 快速排序（medium）

题目链接：912. 排序数组

题目描述：

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

示例 1：

  • 输入：nums = [5,2,3,1]
  • 输出：[1,2,3,5]

示例 2：

  • 输入：nums = [5,1,1,2,0,0]
  • 输出：[0,0,1,1,2,5]
解法（数组分三块 + 随机基准元素的快速排序）

算法思路：

快速排序的核心在于“分区”：将数据按基准元素划分为小于基准、等于基准和大于基准的三部分。通过分治的思想，递归对两侧的分区进行排序。

  1. 随机选择基准元素：

    • 快速排序的效率受基准元素的选取影响。若基准选取不佳，递归的深度增加，影响排序性能。（具体证明详见《算法导论》）
    • 在 getRandom 函数中，使用随机数来生成基准下标，这样在数据量大或元素重复较多的情况下，能有效避免最坏情况。

  2. 三分区思想：

    • 类似于荷兰国旗问题，将数组划分为小于基准、等于基准和大于基准的三部分。
    • 使用三个指针来划分区间：
      • left 指向小于基准的部分末尾。
      • right 指向大于基准的部分起始。
      • i 用于遍历数组，根据当前值的大小，决定其在三分区的位置。

  3. 递归排序左右分区：

    • 对于小于基准和大于基准的部分，递归应用快速排序，最终实现数组的整体有序。
C++ 代码实现
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL)); // 初始化随机数种子
        qsort(nums, 0, nums.size() - 1);
        return nums;
    }

    // 快速排序
    void qsort(vector<int>& nums, int l, int r) {
        if (l >= r) return; // 递归终止条件

        // 选择基准元素
        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) i++;                     // 等于基准，跳过
            else swap(nums[--right], nums[i]);                // 移动到大于基准的区域
        }
        
        // 递归处理左右区域
        qsort(nums, l, left);           // 左分区
        qsort(nums, right, r);          // 右分区
    }

    // 随机基准选择
    int getRandom(vector<int>& nums, int left, int right) {
        int r = rand(); // 生成随机数
        return nums[r % (right - left + 1) + left]; // 生成基准的随机下标
    }
};
易错点提示

  1. 递归终止条件：

    • 在快速排序中，l >= r 时停止递归，否则会陷入无限递归。确保左右分区都有终止条件，避免栈溢出。

  2. 随机基准选取：

    • getRandom 中使用 rand() % (right - left + 1) + left 随机生成基准索引，确保基准在 [left, right] 区间内选择，以应对重复数据。

  3. 三分区逻辑：

    • left 表示小于基准的区域末尾，right 表示大于基准的区域起点，i 为当前扫描位置。确保每轮 i 的位置经过判断后处理到对应的区间，避免重复处理或漏处理。
时间复杂度和空间复杂度
  • 时间复杂度：平均 O(n log n)。使用随机基准元素有效避免最坏 O(n^2) 的情况，提升了排序效率。
  • 空间复杂度：O(log n)，主要为递归栈的空间消耗，最坏情况为 O(n)。

1.3 快速选择算法（medium）

题目链接：215. 数组中的第K个最大元素

题目描述：

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

示例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 <= 10^5
  • -10^4 <= nums[i] <= 10^4
解法（快速选择算法）

算法思路：

快速选择算法是快速排序的变种，可以在不完全排序的情况下找到第 k 大的元素，从而将时间复杂度控制在 O(n)。我们通过分区思想来缩小查找范围，避免对整个数组排序。

  1. 分区思想：

    • 快速排序将数组分成三块：小于基准、等于基准和大于基准。快速选择算法基于同样的分区思想，通过选择一个基准元素，将数组划分为左、中、右三部分。
    • 在每次划分后，可以根据每个区域的元素个数，确定第 k 大的元素所在的区域，从而递归地只处理该部分，逐步缩小范围。

  2. 基准元素的随机选择：

    • 为避免最坏情况，使用 getRandom 函数随机选取基准元素位置，生成随机下标，确保基准在 [left, right] 范围内。

  3. 分区计数与递归：

    • 使用 left、right 和 i 指针对数组进行划分：
      • [l, left]：存放小于基准的元素。
      • [left + 1, right - 1]：存放等于基准的元素。
      • [right, r]：存放大于基准的元素。
    • 划分完成后，通过以下判断确定第 k 大元素所在区间：
      • 若 k 小于等于 c（即右侧元素数），则递归在右侧区间 [right, r] 中继续查找；
      • 若 k 位于中间区间，则直接返回基准元素；
      • 否则递归在左侧区间 [l, left] 中继续查找。

【优选算法篇】化繁为简，见素抱朴：从乱象中重构秩序的艺术-LMLPHP

C++ 代码实现
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL)); // 初始化随机数种子
        return qsort(nums, 0, nums.size() - 1, k);
    }

    // 快速选择
    int qsort(vector<int>& nums, int l, int r, int k) {
        if (l == r) return nums[l]; // 递归终止条件

        // 1. 随机选择基准元素
        int key = getRandom(nums, l, r);
        
        // 2. 根据基准元素将数组分三块
        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) i++;                     // 等于基准，跳过
            else swap(nums[--right], nums[i]);                // 移动到大于基准的区域
        }

        // 3. 分情况判断
        int c = r - right + 1;     // 大于基准元素的个数
        int b = right - left - 1;  // 等于基准元素的个数
        if (c >= k) return qsort(nums, right, r, k);          // 查找右侧区间
        else if (b + c >= k) return key;                      // 查找中间区间
        else return qsort(nums, l, left, k - b - c);          // 查找左侧区间
    }

    // 随机基准选择
    int getRandom(vector<int>& nums, int left, int right) {
        return nums[rand() % (right - left + 1) + left];
    }
};
易错点提示

  1. 递归出口控制：

    • if (l == r) return nums[l]; 确保当数组已缩小到单元素时返回该元素，避免陷入无止境的递归。

  2. 基准随机选取：

    • getRandom 中使用 rand() % (right - left + 1) + left 确保基准元素在 [left, right] 区间内随机选取，减少最坏时间复杂度的可能。

  3. 划分后的区域判断：

    • c 表示大于基准的元素个数；b 表示等于基准的元素个数。通过 k 与这些区域大小的比较，递归进入相应的区间，避免不必要的处理。
时间复杂度和空间复杂度
  • 时间复杂度：平均 O(n)。每次选择的基准元素有效缩小搜索范围，递归深度为 log n，总共需遍历 n 个元素。
  • 空间复杂度：O(log n)，用于递归栈的深度开销。

1.4 最小的 k 个数（medium）

题目链接：剑指 Offer 40. 最小的k个数

题目描述：

输入整数数组 arr，找出其中最小的 k 个数。例如，输入 [4,5,1,6,2,7,3,8]，则最小的 4 个数字是 [1,2,3,4]。

示例 1：

  • 输入：arr = [3,2,1], k = 2
  • 输出：[1,2] 或者 [2,1]

示例 2：

  • 输入：arr = [0,1,2,1], k = 1
  • 输出：[0]

限制：

  • 0 <= k <= arr.length <= 10000
  • 0 <= arr[i] <= 10000
解法（快速选择算法）

算法思路：

快速选择算法是快速排序的变体，可以在 O(n) 的时间复杂度下找到最小的 k 个数。通过分区，将数组划分为小于基准、等于基准和大于基准的三部分，逐步缩小查找范围，直到找到前 k 小的元素。

  1. 分区策略：

    • 使用随机基准元素，将数组划分为小于基准、等于基准和大于基准的三部分。
    • 通过计算每个区间的元素个数，判断最小的 k 个数应在哪个区间中，递归地缩小查找范围。

  2. 随机选择基准：

    • 为避免最坏情况，使用 getRandom 函数随机选取基准元素。通过生成随机下标，将其作为当前基准元素，确保划分的高效性。

  3. 递归查找：

    • 在 qsort 中，使用 left、right 和 i 指针对数组进行分区。
    • 划分完成后，确定第 k 小的元素范围：
      • 若左区间元素个数 a 大于 k，则递归左区间；
      • 若左区间加中间区间的元素总数 a + b 大于等于 k，直接返回前 k 个元素；
      • 若 a + b < k，则递归右区间，寻找剩余的 k - a - b 个元素。
C++ 代码实现
class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& nums, int k) {
        srand(time(NULL)); // 初始化随机数种子
        qsort(nums, 0, nums.size() - 1, k);
        return {nums.begin(), nums.begin() + k};
    }

    // 快速选择
    void qsort(vector<int>& nums, int l, int r, int k) {
        if (l >= r) return; // 递归终止条件

        // 1. 随机选择一个基准元素，并进行分区
        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) i++;                     // 等于基准，跳过
            else swap(nums[--right], nums[i]);                // 大于基准的部分
        }

        // 2. 分情况讨论
        int a = left - l + 1;         // 小于基准的元素个数
        int b = right - left - 1;     // 等于基准的元素个数
        if (a > k) qsort(nums, l, left, k);                 // 在左区间查找
        else if (a + b >= k) return;                         // 在前 a + b 个元素中找到结果
        else qsort(nums, right, r, k - a - b);               // 在右区间查找剩余的元素
    }

    // 随机选择基准元素
    int getRandom(vector<int>& nums, int l, int r) {
        return nums[rand() % (r - l + 1) + l];
    }
};
易错点提示

  1. 递归出口：

    • 当 l >= r 时，递归停止，避免无止境递归。

  2. 随机基准选取：

    • 在 getRandom 函数中使用 rand() % (r - l + 1) + l，确保基准元素随机选自 [l, r] 区间。

  3. 分区结果判定：

    • a 为左区间元素个数，b 为等于基准的元素个数：
      • 若 a > k，表示最小的 k 个数在左区间。
      • 若 a + b >= k，表示最小的 k 个数在前两个区间，直接返回。
      • 若 a + b < k，则在右区间查找剩余的元素。
时间复杂度和空间复杂度
  • 时间复杂度：平均 O(n)。通过随机基准，快速缩小查找范围。
  • 空间复杂度：O(log n)，为递归栈的深度开销。

写在最后

以上就是关于【优选算法篇】化繁为简，见素抱朴：从乱象中重构秩序的艺术的内容啦，各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️

【优选算法篇】化繁为简，见素抱朴：从乱象中重构秩序的艺术-LMLPHP

11-17 18:41
Powered by LMLPHP ©2024 Hoshiᅟᅠ      0.001781