【二十六】【算法分析与设计】分治（1）

75. 颜色分类

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

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

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

示例 1：

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

示例 2：

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

提示：

• n == nums.length

• 1 <= n <= 300

• nums[i] 为 0、1 或 2

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

定义区间[0,left][left+1,right-1][right,n-1]。[0,left]区间全是0，[left+1,right-1]全是1，[right+1,n-1]全是2。

不断维护上述区间，从中间割出一段区间定义为待遍历的区间，[0,left][left+1,i-1][i,right-1][right,n-1]。[i,right-1]是待遍历的区间。

初始状态，left=-1,right=n,i=0。

结束遍历时，i>=right。

如果nums[i]==0，位于第一部分，swap(nums[++left], nums[i++]);让第二部分的数和nums[i]交换。交换维护区间意义。

如果nums[i]==1，位于第二部分，直接i++。

如果nums[i]==2，位于第三部分，swap(nums[--right], nums[i]);让待处理的末尾数字与nums[i]交换，维护区间的意义，此时i不用往后移。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int left = -1, right = n;
        for (int i = 0; i < right;) {
            if (nums[i] == 0)
                swap(nums[++left], nums[i++]);
            else if (nums[i] == 1)
                i++;
            else
                swap(nums[--right], nums[i]);
        }
    }
};

初始化：

n：数组的长度。

left：初始化为-1的指针，它表示数组排序后所有元素都应该是0的索引之前。

right：初始化为n的指针，它表示数组排序后所有元素都应该是2的索引之后。

遍历数组：

循环继续，只要当前索引i小于right。

如果nums[i]是0，它会与索引left + 1处的元素交换（将所有0移动到数组的开始部分），然后left和i都增加。

如果nums[i]是1，它已经在正确的位置（left和right之间），所以只增加i。

如果nums[i]是2，它会与索引right - 1处的元素交换（将所有2移动到数组的末尾），然后right减少。注意，在这种情况下，i不增加，因为交换到末端的元素还没有被评估。

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 <= nums.length <= 5 * 10(4)

• -5 * 10(4) <= nums[i] <= 5 * 10(4)

递归函数qsort。定义qsort递归函数，用来给数组nums数组[l,r]区间进行排序。

递归函数出口，如果l>=r此时区间只有1个元素，不需要排序了，直接返回return。

qsort函数逻辑是在[l,r]区间中随机找一个数，作为基准值key。接着对[l,r]区间中值为key的数安放到正确的位置。

定义区间[l,left][left+1,right-1][right,r]。区间的含义分别是小于key，等于key，大于key。区间长度为0开始一直维护到区间长度为r-l+1。

从[left+1,right-1]区间中割裂出一段区间表示待遍历的区间。

定义区间[l,left][left+1,i-1][i,right-1][right,r]。

初始状态，i=l,right=r+1,left=l-1。

结束状态，i>=right。

if (nums[i] < key) swap(nums[++left], nums[i++]);

如果nums[i]<key，表示nums[i]位于区间[l,left]，此时扩展区间长度，交换nums[left+1],nums[i]，交换完之后，left++，i++。因为nums[i]位于区间[l,left]，nums[left+1]位于区间[left+1,i-1]。 else if (nums[i] == key) i++;

如果nums[i]==key,表示nums[i]位于区间[left+1,i-1]，此时直接扩展区间长度即可，i++。 else swap(nums[--right], nums[i]);

如果nums[i]>key,表示nums[i]位于区间[right,r],扩展区间长度，交换nums[right-1],nums[i]，交换完right--,此时不需要i++，因为nums[right-1]是待处理的元素。

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) { // 定义递归函数qsort，排序一个数
        //[0,nid-1][mid,mid,mid][mid+1,n-1]
        if (l >= r)
            return;
        int key = getRandom(nums, l, r); //[0,left-1][left+1,right-1][right,n-1]
        //[0,left][left+1,i-1][i,right-1][right,n-1]
        int i = l;
        int 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 l, int r) {
        int rand1 = rand();
        return nums[(rand1 % (r - l + 1) + l)];
    }
};

sortArray函数：

使用srand(time(NULL))初始化随机种子，以确保每次运行代码时getRandom函数都能产生不同的随机数。

调用qsort函数对整个数组进行排序。

返回排序后的数组。

qsort函数：

是快速排序的递归实现。

首先检查左右指针l和r，以确保当前分区至少包含两个元素（递归基）。

getRandom函数用于选择一个随机的枢轴元素key，这有助于防止针对特定输入顺序的性能退化。

然后进行三向切分：将小于key的元素移到数组左边，等于key的留在中间，大于key的移到右边。

最后，递归地对小于枢轴元素和大于枢轴元素的子数组进行排序。

getRandom函数：

从子数组nums[l..r]中随机选择一个元素作为枢轴。

使用rand()函数生成一个随机数，然后调整范围和偏移，确保它落在l和r之间。

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

给定整数数组 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 <= 10(5)

• -10(4) <= nums[i] <= 10(4)

定义递归函数qsort为在nums数组[l,r]区间中找第k大的数字。

维护递归函数的内部逻辑，在nums[l,r]区间随机选取一个值为key，将值为key的数放到排序后对应的位置上，相当于只给值为key的数进行排序。

定义区间[l,left][left+1,right-1][right,r]分别表示小于key，等于key，大于key。

从[left+1,right-1]全进分割出待遍历的区间。

定义区间[l,left][left+1,i-1][i,right-1][right,r]。

初始状态i=l，left=l-1，right=r+1。

结束状态i>=right。

if (nums[i] < key) swap(nums[++left], nums[i++]);

如果nums[i]<key，表示nums[i]位于区间[l,left]，此时扩展区间长度，交换nums[left+1],nums[i]，交换完之后，left++，i++。因为nums[i]位于区间[l,left]，nums[left+1]位于区间[left+1,i-1]。 else if (nums[i] == key) i++;

如果nums[i]==key,表示nums[i]位于区间[left+1,i-1]，此时直接扩展区间长度即可，i++。 else swap(nums[--right], nums[i]);

如果nums[i]>key,表示nums[i]位于区间[right,r],扩展区间长度，交换nums[right-1],nums[i]，交换完right--,此时不需要i++，因为nums[right-1]是待处理的元素。

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) {
        // 排序nums数组[l,r]区间，只排值为key的数，[l,left][left+1,right-1][right,r]
        //[l,left][left+1,i-1][i,right-1][right,r]
        // 找到区间第k大的元素
        if (l >= r)
            return nums[l];
        int key = getRandom(nums, l, r);
        int i = l;
        int 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]);
        }
        int c = r - right + 1, 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 l, int r) {
        int rand1 = rand();
        int index = rand1 % (r - l + 1) + l;
        return nums[index];
    }
};

findKthLargest函数：

通过调用srand(time(NULL))初始化随机种子，确保每次执行时都能获得不同的随机数。

调用qsort函数查找并返回数组中第k大的元素。

qsort函数：

此函数是算法的核心，执行快速选择操作。它不是对整个数组进行排序，而是定位到第k大的元素。

参数l和r定义了当前考虑的数组部分的边界，k是你想找的元素的大小顺序。

如果l等于r，这意味着我们已经缩小到一个元素，直接返回该元素。

getRandom用于选择当前区间内的一个随机枢纽元素key。

接下来，数组被分成三部分：小于key的、等于key的和大于key的元素。这通过与key的比较并交换元素来实现。

计算出大于枢轴（key）的元素数量（c），以及等于枢轴的元素数量（b）。

根据这些计数和k的值，决定下一步应该在哪部分继续搜索：

如果大于枢轴的元素数量c大于或等于k，则在右侧（较大元素那侧）继续搜索。

如果加上等于枢轴的元素数量后总数仍大于或等于k，则已经找到第k大的元素，它等于key。

否则，在左侧（较小元素那侧）继续搜索，并相应地更新k的值。

getRandom函数：

在l和r确定的区间内生成一个随机索引，并返回该索引处的元素作为枢轴元素。这有助于防止算法在最坏的情况下（例如，当数组已排序时）表现不佳。

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

定义递归函数qsort将nums数组[l,r]区间最小的k个数全部放在[0,k-1]区间上。

维护递归函数的内部逻辑，在nums[l,r]区间随机选取一个值为key，将值为key的数放到排序后对应的位置上，相当于只给值为key的数进行排序。

定义区间[l,left][left+1,right-1][right,r]分别表示小于key，等于key，大于key。

从[left+1,right-1]全进分割出待遍历的区间。

定义区间[l,left][left+1,i-1][i,right-1][right,r]。

初始状态i=l，left=l-1，right=r+1。

结束状态i>=right。

if (nums[i] < key) swap(nums[++left], nums[i++]);

如果nums[i]<key，表示nums[i]位于区间[l,left]，此时扩展区间长度，交换nums[left+1],nums[i]，交换完之后，left++，i++。因为nums[i]位于区间[l,left]，nums[left+1]位于区间[left+1,i-1]。 else if (nums[i] == key) i++;

如果nums[i]==key,表示nums[i]位于区间[left+1,i-1]，此时直接扩展区间长度即可，i++。 else swap(nums[--right], nums[i]);

如果nums[i]>key,表示nums[i]位于区间[right,r],扩展区间长度，交换nums[right-1],nums[i]，交换完right--,此时不需要i++，因为nums[right-1]是待处理的元素。

class Solution {
public:
    vector<int> inventoryManagement(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;
        int key = getRandom(nums, l, r);
        // 排序nums数组中[l,r]，将k个小的数放到正确位置
        //[l,left][left+1,right-1][right,r]
        //[l,left][left+1,i-1][i,right-1][right,r]
        int i = l;
        int 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]);
        }
        int a = left - l + 1;
        int b = right - left - 1;
        if (a > k)
            qsort(nums, l, left, k);
        else if (a + b >= k)
            return;
        else
            qsort(nums, right, r, k - a - b);
    }
    int getRandom(vector<int> nums, int l, int r) {
        int rand1 = rand();
        int index = rand1 % (r - l + 1) + l;
        return nums[index];
    }
};

inventoryManagement函数:

初始化随机数种子，以确保getRandom函数能产生不同的随机数。

调用qsort函数，不是为了完全排序nums数组，而是为了将最小的k个数置于数组的开始位置。

返回数组的前k个元素，这些元素是数组中最小的k个数。

qsort函数:

实现了快速选择的逻辑，但有所修改以满足特定需求。

数组被分为三个部分：小于枢轴key的、等于key的和大于key的元素。

left和right是分隔这三个部分的界限。

a是小于枢轴的元素数量，b是等于枢轴的元素数量。

如果a（小于枢轴的元素数量）大于k，说明我们只需要对左边的部分进行递归操作。

如果a + b（小于或等于枢轴的元素数量）大于或等于k，那么已经找到了最小的k个数，它们都位于数组的左侧，因此不需要进一步操作。

如果上述两种情况都不满足，说明需要的k个最小数中还包括一些大于枢轴的数，所以需要对右侧部分进行递归操作，并调整k的值为k - a - b，因为我们已经确定了a + b个数是属于最小的k个数之一。

getRandom函数:

产生一个在l和r之间的随机索引，并返回该索引处的值作为枢轴值。这有助于防止算法性能退化到最坏情况，尤其是在数组已经有序或接近有序的情况下。

结尾

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。

谢谢您的支持，期待与您在下一篇文章中再次相遇！