分治算法(三分快排 + 归并排序深入思维)万字

2024-01-03 13:31:46
(阅读本文一定要具备二分快排的算法思维)将会直接从三分快排入手

基本思想

??分治算法(基于递归)将大问题分解成与原问题相似的子问题,递归地解决每个子问题,最后将子问题的解合并成大问题的解。分割的解法使得可以明显降低问题的复杂度。
??三分快排:对于二分快排的缺陷(元素全部相同排序)的优化时间复杂度为O(n)。???

引入算法题

??此处就是面对 二分快速排序 + 归并排序深入 学习,如果只是想入门分治算法,那么掌握普通的 二分快速排序 + 归并排序 即可。

三分快排思维

颜色分类(三分快排入门必备)

链接: https://leetcode.cn/problems/sort-colors/

??给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。
??我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
??必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1:
?输入:nums = [2,0,2,1,1,0]
?输出:[0,0,1,1,2,2]

题目分析:

??此题是 移动零 的double版本,属于三指针,三指针与双指针一样都是区域的划分问题移动零(双指针讲解)
在这里插入图片描述
解题:

  • 三指针:
  • cur:遍历数组。
  • left:标记 0 区域的最右侧。
  • right:标记 2 区域的最左侧。
  • 区域划分:
  • [0, left]:全是 0 。
  • [left + 1, cur - 1]:全是 1 。
  • [cur, right - 1]:待判断。
  • [right, nums.size() - 1]:全是 2 。
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int cur = 0, left = -1, right = nums.size();
        while(cur < right)
        {
            if(nums[cur] == 0)
                swap(nums[++left], nums[cur++]);
            else if(nums[cur] == 1)
                cur++;
            else
                // 此处cur并不能++,因为right - 1并未被判断
                swap(nums[--right], nums[cur]);
        }
    }
};

三分快排

链接: https://leetcode.cn/problems/sort-an-array/description/

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

示例 1:
?输入:nums = [5,2,3,1]
?输出:[1,2,3,5]

题目分析:

??就是可能存在大量数据重复的排序题,所以需要使用到三分快排

解题:

  • 用随机方式选基准元素
    ??优化:用随机方式选择基准元素的(必要性)《算法导论》中通过概率求期望,时间复杂度可以渐进到 N l o g N N{logN} NlogN(对于二分快排)。
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        quick_sort(nums, 0, nums.size() - 1);
        return nums;
    }

    void quick_sort(vector<int>& nums, int prev, int tail)
    {
        if(prev >= tail)  // 有可能出现如没有<的值,于是tail = left = -1
            return;
		// 数组分三块
        int key = nums[rand_num(prev, tail)];
        int left = prev - 1, right = tail + 1;
        int cur = prev;
        while(cur < right)
        {
            if(nums[cur] < key)
                swap(nums[++left], nums[cur++]);
            else if(nums[cur] == key)
                cur++;
            else
                swap(nums[--right], nums[cur]);
        }

		// [prev, left](<)  [left + 1, right - 1](==)  [right, tail](>)
        quick_sort(nums, prev, left);
        quick_sort(nums, right, tail);
    }

    int rand_num(int prev, int tail)
    {
        int r = rand();
        return r % (tail - prev + 1) + prev;
    }
};

初步识别思路???

  • 对于一个nums数组,三分快排会将数据分割为 [<key][=key][>key] or [>key][=key][<key] ,所以其是比二分快排分割更有性价比的,可以通过此分割实现数据分割看待

数组中的第K个最大元素

链接: https://leetcode.cn/problems/kth-largest-element-in-an-array/description/

??给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
??请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
??你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

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

题目分析:

??此处要求时间复杂度为O( N N N),所以正常的堆排(时间复杂度O( N l o g N N{logN} NlogN))已经无法解决这个问题。而三分快排的方式可以使用O( N N N)的时间找到,《算法导论》有严格的证明。

解题:

在这里插入图片描述

  • 状态划分:题需要第 k 大
    1、c >= k → \rightarrow [right, tail]查找第 k 个
    2、b + c >= k → \rightarrow 返回
    3、b + c < k → \rightarrow [prev, left]查找第 k - b - c 个
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(nullptr));
        q_sort(nums, 0, nums.size() - 1, k);
        return nums[nums.size() - k];
    }

    void q_sort(vector<int>& nums, int prev, int tail, int k)
    {
        if(prev >= tail)
            return;

        int key = nums[rand_num(prev, tail)];
        int left = prev - 1, right = tail + 1;
        int cur = prev;
        while(cur < right)
        {
            if(nums[cur] < key)
                swap(nums[++left], nums[cur++]);
            else if(nums[cur] == key)
                cur++;
            else
                swap(nums[--right], nums[cur]);
        }

        // 判断第k大属于哪个区域
        int b = right - left - 1, c = tail - right + 1;
        if(k <= c)
            q_sort(nums, right, tail, k);
        else if(k <= b + c)
            return;
        else
            q_sort(nums, prev, left, k - b - c);
    }

    int rand_num(int prev, int tail)
    {
        return rand() % (tail - prev + 1) + prev;
    }
};

库存管理 III

链接: https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/description/

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

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

题目分析:

??不多说了,就是上一题的升级,进一步不是 第K大/小,而是 K大/小

解题:

  • 状态划分:题需要 k 小
    1、a > k → \rightarrow [prev, left]查找 k 个
    2、a + b >= k → \rightarrow 返回
    3、a + b < k → \rightarrow [right, tail]查找 k - a - b 个
class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(nullptr));
        q_sort(stock, 0, stock.size() - 1, cnt);
        return {stock.begin(), stock.begin() + cnt};
    }

    void q_sort(vector<int>& nums, int prev, int tail, int cnt)
    {
        if(prev >= tail)
            return;

        int key = nums[rand_num(prev, tail)];
        int left = prev - 1, right = tail + 1;
        int cur = prev;
        while(cur < right)
        {
            if(nums[cur] < key)
                swap(nums[++left], nums[cur++]);
            else if(nums[cur] == key)
                cur++;
            else
                swap(nums[--right], nums[cur]);
        }

        // 判断最小的cnt个属于哪个区域
        int a = left + 1 - prev, b = right - left - 1;
        if(a > cnt)
            q_sort(nums, prev, left, cnt);
        else if(a + b >= cnt)
            return;
        else
            q_sort(nums, right, tail, cnt - a - b);
    }

    int rand_num(int prev, int tail)
    {
        return rand() % (tail - prev + 1) + prev;
    }
};

归并排序思维

初步识别思路???

  • 对于一个nums数组,以前后关系所对应的数量类似的要求,就可以尝试使用归并排序时:「左半部分排序」+「右半部分排序」= 上个递归的「左半部分排序」or「右半部分排序」的特性,完成排序时分析,实现 O( N l o n g N NlongN NlongN) 重合归并排序的时间复杂度。
  • 根据分析:无需现在看懂,此处是后续题的总结,直接看题即可。

注意: 看似一摸一样,就是换一个方向,但是从程序员的角度,如此调换截然不同!!!

  • 策略一:计算当前元素后面,有多少元素的比我小nums[left] > nums[right],右部分个数 - 降序重点降序,需求[left] > [right, 最后]
    在这里插入图片描述
  • 策略二:计算当前元素之前,有多少元素的比我大nums[right] < nums[left],左部分个数 - 升序重点升序,需求[i, mid] > [j]
    在这里插入图片描述

归并排序

链接: https://leetcode.cn/problems/sort-an-array/description/

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

示例 1:
?输入:nums = [5,2,3,1]
?输出:[1,2,3,5]

题目分析:

??这就是前面三分快排所解的题,此处目的是再写一遍归并排序的算法。

解题:

  • 归并排序的流程充分的体现了「分而治之」的思想:
    • :将数组?分为?为两部分,?直分解到数组的长度为 1 ,使整个数组的排序过程被分为「左半部分排序」 + 「右半部分排序」
    • :将两个较短的「有序数组合并成?个长的有序数组」,?直合并到最初的长度。
class Solution {
    vector<int> tmp;
public:
    vector<int> sortArray(vector<int>& nums) {
        int size = nums.size();
        tmp.resize(size);
        merge_sort(nums, 0, size - 1);
        return nums;
    }

    void merge_sort(vector<int>& nums, int prev, int tail)
    {
        if(prev >= tail)
            return;

        int mid = prev + ((tail - prev) >> 1);

        // 进行递归
        merge_sort(nums, prev, mid);
        merge_sort(nums, mid + 1, tail);

        // 进行排序
        int left = prev, right = mid + 1;
        int i = 0; // tmp的映射位置
        while(left <= mid && right <= tail)
        {
            tmp[i++] = nums[left] <= nums[right] ? nums[left++] : nums[right++];
        }
        // 将数据遍历完
        while(left <= mid) tmp[i++] = nums[left++];
        while(right <= tail) tmp[i++] = nums[right++];

        // 还原
        for(int i = prev; i <= tail; i++)
            nums[i] = tmp[i - prev];
    }
};

交易逆序对的总数

链接: https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/description/

??在股票交易中,如果前一天的股价高于后一天的股价,则可以认为存在一个「交易逆序对」。请设计一个程序,输入一段时间内的股票交易记录 record,返回其中存在的「交易逆序对」总数。

示例 1:
?输入:record = [9, 7, 5, 4, 6]
?输出:8
?解释:交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

题目分析:

??此题,如果用暴力解题的方法找逆序对,那么就是两层for循环,时间复杂度O( N 2 N^2 N2)。此题最好的方式是采用归并排序的特性来解决,达到时间复杂度O( l o g N logN logN)。

注意: 需要的是前者 > 后者,并不是一大一小任意组合!!!

解题:

  • 归并排序能够保证在一层递归中的左右子数组是有序的!
    在这里插入图片描述

??当我们确定,左右子数组其自身一定是有序的,于是便可以评定此特性求解,达到解题时间复杂度与归并排序的时间复杂度所重合。
在这里插入图片描述

??我们需要明确一个点, a 与 c 两个段的所有数据一定是小于 b 与 d 两个段的所有数据。(如果想不清一定需要明确:一层递归中左右子数组其自身一定是有序的

  • 场景模拟(此时:按升序排序)
    • nums[left] <= nums[right]
      • 此时left++;,因为我们渴望[left, mid] > [right]的数据,此处明显不符合。
    • nums[left] > nums[right]
      • 此时ret += mid - left + 1; right++;,这就是渴望的[left, mid] > [right]的数据,此时就能够知道 右取一个数据左取一个数据 能组成的一共的逆序对个数。

??此处如果对于分治算法(归并排序)掌握完全此处就已经是解答。

但:提到的都是 `右取一个数据` 与 `左取一个数据` 组成的,右部分的组成 / 左部分的组成就不算了吗?

??这就是分治算法的特性,此处的右部分的组成 / 左部分的组成,在上一个递归不还是
右取一个数据左取一个数据 组成的吗?所以看似需要求整体的话是:左部分的逆序对 + 右部分的逆序对 + 左右各取一个的逆序对 == 左右各取一个的逆序对(真正实际需要的!)

思考升级: 此处使用的是利用归并排序升序,如果是降序呢? (会在升序后给出解答,建议进行尝试)

  • 将代码文字化
  • 定义递归出口: left >= right 时,直接返回;
  • 划分区间: 根据中点 mid,将区间划分为 [prev, mid][mid + 1, tail]
  • 统计左右两个区间逆序对的数量:(此处就是递归到下一层递归,求该区间分半之后的左右各取一个的逆序对
    • 统计左边区间 [prev, mid] 中每个元素对应的逆序对的数量到 ret 中,并排序;
    • 统计右边区间 [mid + 1, tail] 中每个元素对应的逆序对的数量到 ret 中,并排序。
  • 合并左右两个有序区间,并且统计出逆序对的数量:
    • 辅助数组:tmp
    • 初始化遍历数组的指针:left = prev(遍历左半部分数组)right = mid + 1(遍历右半边数
      组)ret = 0(逆序对数量)
    • 循环合并区间:
      • nums[left] <= nums[right]
        • 此时left++;
      • nums[left] > nums[right]
        • 此时ret += mid - left + 1; right++;
    • 将辅助数组的内容替换到原数组中去;
class Solution {
    vector<int> tmp;
    int ret = 0;
public:
    int reversePairs(vector<int>& record) {
        tmp.resize(record.size());
        merge_sort(record, 0, record.size() - 1);
        return ret;
    }

    void merge_sort(vector<int>& nums, int prev, int tail)
    {
        if(prev >= tail)
            return;
        
        int mid = prev + ((tail - prev) >> 1);

        // 进行递归
        merge_sort(nums, prev, mid);
        merge_sort(nums, mid + 1, tail);

        // 进行排序 + 计算逆序对 - 升序
        int left = prev, right = mid + 1;
        int i = 0;
        while(left <= mid && right <= tail)
        {
            if(nums[left] <= nums[right])
                tmp[i++] = nums[left++];
            else
            {
                ret += mid - left + 1;
                tmp[i++] = nums[right++];
            }
        }

        while(left <= mid) tmp[i++] = nums[left++];
        while(right <= tail) tmp[i++] = nums[right++];

        // 归还数据
        for(int i = prev; i <= tail; i++)
        {
            nums[i] = tmp[i - prev];
        }
    }
};

#: 归并排序 降序

??需要明确一个点,以升序为例:我们是让一个数据和一个区域相组合,那么我们就需要保证,组合计算过后的那单一数据必须移动,不然就会出现重复逆序对。

  • 升序易错的错例为例:
    在这里插入图片描述
    • nums[left] < nums[right]
      • 此时ret += mid - left + 1; left++;
    • nums[left] >= nums[right]
      • 此时right++;

??看似是可以的,当nums[left] < nums[right]时能够使得 [头, left] < [right] 进行逆序对的组合,但是 小大 组合,并不是 大小 组合的逆序对。而且逻辑上万一同样的nums[left + 1] < nums[right],那么就会 [头, left + 1] < [right] 进行组合,导致[头, left]被计算两次,也是不行的。

  • 降序的正确做法
    在这里插入图片描述
  • 场景模拟(此时:按降序排序)
    • nums[left] <= nums[right]
      • 此时right++;,因为我们渴望[left] > [right, tail]的数据,此处明显不符合。
    • nums[left] > nums[right]
      • 此时ret += tail - right + 1; left++;,这就是渴望的[left] > [right, tail]的数据,此时就能够知道 右取一个数据左取一个数据 能组成的一共的逆序对个数。
class Solution {
    vector<int> tmp;
public:
    int reversePairs(vector<int>& record) {
        tmp.resize(record.size());
        return merge_sort(record, 0, record.size() - 1);
    }
    int merge_sort(vector<int>& nums, int prev, int tail)
    {
        int ret = 0;
        if(prev >= tail)
            return 0;

        int mid = prev + ((tail - prev) >> 1);

        ret += merge_sort(nums, prev, mid);
        ret += merge_sort(nums, mid + 1, tail);

        int i = 0;
        int left = prev, right = mid + 1;
        // 降序版本
        while(left <= mid && right <= tail)
        {
            if(nums[left] <= nums[right])
            {
                tmp[i++] = nums[right++];
            }
            else if(nums[left] > nums[right])
            {
                ret += tail - right + 1;
                tmp[i++] = nums[left++];
            }
        }
        while(left <= mid) tmp[i++] = nums[left++];
        while(right <= tail) tmp[i++] = nums[right++];
        for(int j = prev; j <= tail; j++)
            nums[j] = tmp[j - prev];

        return ret;
    }
};

总结:

  • 策略一: 左侧有多少值,比右侧定值大 - 升序。
  • 策略二: 右侧有多少值,比左侧定值小 - 降序。

计算右侧小于当前元素的个数

链接: https://leetcode.cn/problems/count-of-smaller-numbers-after-self/description/

??给你一个整数数组 nums ,按要求返回一个新数组 counts 。数组 counts 有该性质: counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1:
?输入:nums = [5,2,6,1]
?输出:[2,1,1,0]
?解释:

?5 的右侧有 2 个更小的元素 (2 和 1)
?2 的右侧仅有 1 个更小的元素 (1)
?6 的右侧有 1 个更小的元素 (1)
?1 的右侧有 0 个更小的元素

题目分析:

??此题看似困难,但其实就是上题的策略之一:策略二: 右侧有多少值,比左侧定值小 - 降序。

解题:

  • 此题重点
    与上题区别,就是需要根据 nums数组中数据的原始下标进行记录右侧有多少值,比左侧定值小。
    同理,也就是如使用 nums + tmp_nums组合 一样,为原始下标记录也配一个 tmp_index + index组合
class Solution {
    vector<int> tmp_nums;
    vector<int> index;
    vector<int> tmp_index;

public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        tmp_nums.resize(n);
        index.resize(n);
        tmp_index.resize(n);

        // 记录下标
        for(int i = 0; i < n; i++)
            index[i] = i;

        // 返回数组
        vector<int> ret;
        ret.resize(n);

        // 归并排序解题
        merge(nums, 0, n - 1, ret);

        return ret;
    }

    void merge(vector<int>& nums, int prev, int tail, vector<int>& ret)
    {
        if(prev >= tail)
            return;
        
        int mid = prev + ((tail - prev) >> 1);
        merge(nums, prev, mid, ret);
        merge(nums, mid + 1, tail, ret);

        int i = 0;
        int left = prev, right = mid + 1;

        // 降序解题
        while(left <= mid && right <= tail)
        {
            if(nums[left] <= nums[right])
            {
                tmp_nums[i] = nums[right];
                tmp_index[i++] = index[right++];
            }
            else
            {
                ret[index[left]] += tail - right + 1;
                tmp_nums[i] = nums[left];
                tmp_index[i++] = index[left++];
            }
        }
        while(left <= mid)
        {
            tmp_nums[i] = nums[left];
            tmp_index[i++] = index[left++];
        }
        while(right <= tail)
        {
            tmp_nums[i] = nums[right];
            tmp_index[i++] = index[right++];
        }

        for(int j = prev; j <= tail; j++)
        {
            nums[j] = tmp_nums[j - prev];
            index[j] = tmp_index[j - prev];
        }
    }
};

翻转对

链接: https://leetcode.cn/problems/reverse-pairs/description/

??给定一个数组 nums ,如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
??你需要返回给定数组中的重要翻转对的数量。

示例 1:
?输入: [1,3,2,3,1]
?输出: 2

题目分析:
??此题与逆序对极其相似,只不过一个是i<j && nums[i] > 2*nums[j],另一个是i<j && nums[i] > nums[j]
解题:
??前面的题如:逆序对,是因为比较的值是一对一的,所以能与归并排序所完美的结合。而此处需要的是 i<j && nums[i] > 2*nums[j] ,是无保证 [left] > [right, tail] && 一定符合 nums[left] > 2*nums[right] 。所以其是无法与归并排序进行重合,需要提前计算。
??可以达到一次递归,提前计算的重要翻转对数量时间复杂度为O( N N N)。

  • 根据分析:
  • 策略一:计算当前元素后面,有多少元素的两倍比我小nums[i] > 2*nums[j] - 降序
  • 策略二:计算当前元素之前,有多少元素的一半比我大nums[j] < nums[i] / 2.0 - 升序

注意: 看似一摸一样,就是换一个方向,但是从程序员的角度,如此调换截然不同!!!

??通过前一步的分析,我们可以知道,之所以其无法与归并排序所完美的结合,就是因为其不是如i<j && nums[i] > 2*nums[j]的数据对应,所以重点是改变的一方对应的范围

  • nums[i] > 2*nums[j]的重点是> 2*nums[j],就是右半部分,所以需要右半部分越来越小 - 降序
  • nums[j] < nums[i] / 2.0的重点是< nums[i] / 2.0,就是左半部分,所以需要左半部分越来越大 - 升序

说白了就是:利用单调性,以递增 / 递减,使用「相向双指针」来解决 - 不回退,同时向一个方向进行移动。

策略一:利用降序排序

class Solution {
    vector<int> tmp;

public:
    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());

        return merge(nums, 0, nums.size() - 1);
    }

    int merge(vector<int>& nums, int prev, int tail)
    {
        if(prev >= tail)
            return 0;
        
        int ret = 0;
        int mid = prev + ((tail - prev) >> 1 );

        ret += merge(nums, prev, mid);
        ret += merge(nums, mid + 1, tail);

        int i = 0;
        int left = prev, right = mid + 1;

        // 计算重要翻转对 - 降序排序 - 对应 > nums[j] * 2 - 关注:右半部分
        int i_left = left, j_right = right;
        while(i_left <= mid)
        {
            while(j_right <= tail && nums[i_left] <= (long long)2 * nums[j_right])
            {
                j_right++;
            }
            if(i_left > mid)
                break;
            ret += tail - j_right + 1;
            i_left++;
        }

        // 降序排序 - 对应 > nums[j] * 2
        while(left <= mid && right <= tail)
        {
            if(nums[left] <= nums[right])
                tmp[i++] = nums[right++];
            else
                tmp[i++] = nums[left++];
        }

        while(left <= mid) tmp[i++] = nums[left++];
        while(right <= tail) tmp[i++] = nums[right++];
        for(int i = prev; i <= tail; i++)
            nums[i] = tmp[i - prev];

        return ret;
    }
};

策略二:利用升序排序

class Solution {
    vector<int> tmp;

public:
    int reversePairs(vector<int>& nums) {
        tmp.resize(nums.size());

        return merge(nums, 0, nums.size() - 1);
    }

    int merge(vector<int>& nums, int prev, int tail)
    {
        if(prev >= tail)
            return 0;
        
        int ret = 0;
        int mid = prev + ((tail - prev) >> 1 );

        ret += merge(nums, prev, mid);
        ret += merge(nums, mid + 1, tail);

        int i = 0;
        int left = prev, right = mid + 1;

        // 计算重要翻转对 - 升序排序 - 对应 < nums[i] / 2.0 - 关注:左半部分
        int i_left = left, j_right = right;
        while(j_right <= tail)
        {
            while(i_left <= mid && nums[j_right] >= nums[i_left] / 2.0)
            {
                i_left++;
            }
            if(i_left > mid)
                break;
            ret += mid - i_left + 1;
            j_right++;
        }

        // 升序排序 - 对应 < nums[i] / 2.0
        while(left <= mid && right <= tail)
        {
            if(nums[left] >= nums[right])
                tmp[i++] = nums[right++];
            else
                tmp[i++] = nums[left++];
        }

        while(left <= mid) tmp[i++] = nums[left++];
        while(right <= tail) tmp[i++] = nums[right++];
        for(int i = prev; i <= tail; i++)
            nums[i] = tmp[i - prev];

        return ret;
    }
};

文章来源:https://blog.csdn.net/weixin_64609308/article/details/135138226
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。