【C++算法】分治（快排 & 归并）

用户11316099

发布于 2024-10-15 20:38:19

1120

发布于 2024-10-15 20:38:19

文章被收录于专栏：学习之路

1. 引言

1.1 分治算法思想

☘️☘️☘️规模为n的原问题的解无法直接求出，进行问题规模缩减，划分子问题（这里子问题相互独立而且和原问题解的性质是相同的，只是问题规模缩小了）。如果子问题的规模仍然不够小，再进行子问题划分，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止，最后求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。

1.2 分治算法适用条件

分治算法所能解决的问题一般具有以下几个特征：

原问题的规模缩小到一定的程度就可以很容易地解决
原问题可以分解为若干个规模较小的相同问题，即原问题具有最优子结构性质
利用原问题分解出的子问题的解可以合并为原问题的解
原问题分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题（这条特征涉及到分治法的效率，如果各个子问题不独立，也就是子问题划分有重合部分，则分治法要重复的求解1公共子问题的解，此时虽然也可用分治法，但采用动态规划更好）

经典例题如下：

2. 快排

2.1 颜色分类

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

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

思路： 三指针，用 i 来遍历数组，left 标记 0 区域的最右侧，right 标记 2 区域的最左侧

[0，left]：全部都是 0
[left + 1，i - 1]：全都是 1
[i，right - 1]：待扫描元素
[right，n - 1]：全都是2

然后分类讨论，对于nums[ i ]. 如果为 0，则 swap(nums[++left]，nums[ i++ ]) 这里 i++原因是因为交换后的数已经被扫描过了如果为 1，则 i++. 如果为 2，则 swap(nums[--right]，nums[ i ]) 注：由于下标从0开始，那么对于left应该初始化为-1

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int l = -1, r = n, i = 0;
        while (i < r)
        {
            if (nums[i] == 0)swap(nums[++l], nums[i++]);
            else if (nums[i] == 1) i++;
            else if (nums[i] == 2) swap(nums[--r], nums[i]);

        }
    }
};

2.2 排序数组

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

方法一：（数组分两块）

思路： 找个基准值，把一个大数组分成两个小数组

class Solution {
public:

    void QuickSort(vector<int>& q, int l, int r)
    {
        if (l >= r) return;

        int x = q[l + r >> 1];
        int i = l - 1, j = r + 1;
        while (i < j)
        {
            do i++; while (q[i] < x);
            do j--; while (q[j] > x);
            if (i < j)swap(q[i], q[j]);
        }
        QuickSort(q, l, j);
        QuickSort(q, j + 1, r);
    }

    vector<int> sortArray(vector<int>& nums) {
        auto q = nums;
        int n = nums.size();
        QuickSort(q, 0, n - 1);
        return q;
    }
};

方法二：数组分三块 + 随机选择基准元素

思路：数组分三块 + 随机选择基准元素

class Solution {
public:

    int getRandom(vector<int>& nums, int left, int right) {
        int k = rand();
        return nums[k % (right - left + 1) + left];
    }

    vector<int> sortArray(vector<int>& nums)
    {
        srand(time(NULL));
        QuickSort(nums, 0, nums.size() - 1);
        return nums;
    }

    void QuickSort(vector<int>& nums, int l, int r)
    {
        if (l >= r) return;

        int k = getRandom(nums, l, r);
        int i = l, left = l - 1, right = r + 1;
        while (i < right)
        {
            if (nums[i] < k) swap(nums[++left], nums[i++]);
            else if (nums[i] == k) i++;
            else swap(nums[--right], nums[i]);
        }
        QuickSort(nums, l, left);
        QuickSort(nums, right, r);
    }
};

2.3 数组中的第K个最大元素

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

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

思路：数组分三块 + 选择基准元素

class Solution {
public:
	int sort(vector<int>& nums, int l,int r, int k)
	{
		if (l == r) return nums[l];

		// 1. 找基准元素
		int key = nums[l + r >> 1];
		// 2. 根据基准元素把数组分三块
		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]);
		}
		// 3. 分情况讨论
		int c = r - right + 1, b = right - left - 1;
		if (c >= k) return sort(nums, right, r, k);
		else if (b + c >= k) return key;
		else return sort(nums, l, left, k - b - c);


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

2.4 库存管理 III

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

思路： 该题目本质就是求数组的最小 k 个元素

class Solution {
public:
    void sort(vector<int>& nums, int l, int r, int k) {
        if (l >= r) return;
        // 1. 基准元素 + 数组分块
        int key = nums[l + r >> 1];
        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, b = right - left - 1;
        if (a > k) sort(nums, l, left, k);
        else if (a + b >= k) return;
        else sort(nums, right, r, k - a - b);
    }

    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        sort(stock, 0, stock.size() - 1, cnt);
        return { stock.begin(),stock.begin() + cnt };
    }
};

3. 归并

3.1 归并排序

class Solution {
public:
    int tmp[100005];

    void mergesort(vector<int>& nums, int l, int r){
        if (l >= r) return;

        // 1. 根据中间元素，划分区间
        int mid = l + r >> 1;

        // 2. 处理左右两部分
        mergesort(nums, l, mid), mergesort(nums, mid + 1, r);

        // 3. 处理一左一右情况
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r)
        {
            if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
            else tmp[k++] = nums[j++];
        }

        // 4. 处理剩下排序过程
        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= r) tmp[k++] = nums[j++];

        // 5. 更新原数组
        for (i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];
    }

    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        mergesort(nums, 0, n - 1);
        return nums;
    }
};

3.2 交易逆序对的总数

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

对于数列的第 i 个和第 j 个元素，如果满足 i < j 且 a[i] > a[j]，则其为一个逆序对。重要的地方在于，一个元素可以不只是在一个逆序对中存在。如果 k > j > i 且 a[i] > a[j] > a[k]，那么这里有两个含 a[i] 的逆序对，分别是 (a[i], a[j]) 和 (a[i], a[k]), a[i]是可以使用多次的。那么第二步是分析问题，这里我们可以使用分治法解决问题。我们将序列从中间分开，将逆序对分成三类：

两个元素都在左边；
两个元素都在右边；
两个元素一个在左一个在右；

因此这就是我们算法的大致框架：计算逆序对的数量（序列）： 1. 递归算左边的； 2. 递归算右边的； 3. 算一个左一个右的； 4. 把他们加到到一起。

class Solution {
public:
    int tmp[100005];

    int mergesort(vector<int>& nums, int l, int r) 
    {
        if (l >= r) return 0;
        int mid = l + r >> 1;
        int res = mergesort(nums, l, mid) + mergesort(nums, mid + 1, r);

        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r)
        {
            if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
            else {
                tmp[k++] = nums[j++];
                res += mid - i + 1; //区间内逆序数目
            }
        }

        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= r) tmp[k++] = nums[j++];

        for (i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];
        return res;
    }

    int reversePairs(vector<int>& record) {
        return mergesort(record, 0, record.size() - 1);
    }
};

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

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

思路：该题与上题算逆序对数目类似，需要用个数组来存 nums 的下标当前元素后面，有多少个比我小。（降序）

class Solution {
public:
    int tmpNums[500005];
    int tmpIndex[500005];
    vector<int> ret;
    vector<int> index; //记录nums 当前元素的原始下标

    void mergesort(vector<int>& nums, int l, int r) {
        if (l >= r) return;

        // 1. 根据中间元素，划分区间
        int mid = l + r >> 1;

        // 2. 处理左右两部分
        mergesort(nums, l, mid), mergesort(nums, mid + 1, r);

        // 3. 处理一左一右情况
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r)
        {
            if (nums[i] <= nums[j]) {
                tmpIndex[k] = index[j];
                tmpNums[k++] = nums[j++];
            }
            else {
                ret[index[i]] += r - j + 1;
                tmpIndex[k] = index[i];
                tmpNums[k++] = nums[i++];
            }
        }

        // 4. 处理剩下排序过程
        while (i <= mid) {
            tmpIndex[k] = index[i];
            tmpNums[k++] = nums[i++];
        }
        while (j <= r) {
            tmpIndex[k] = index[j];
            tmpNums[k++] = nums[j++];
        }

        // 5. 更新原数组
        for (i = l, j = 0; i <= r; i++, j++) {
            index[i] = tmpIndex[j];
            nums[i] = tmpNums[j];
        }
    }

    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        ret.resize(n);
        index.resize(n);

        // 初始化一下 index 数组
        for (int i = 0; i < n; i++) index[i] = i;
        mergesort(nums, 0, n - 1);
        
        return ret;
    }
};

3.4 翻转对

给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。

思路：方法一（降序）：找当前元素后面，有多少元素的两倍比我小，res += r - j + 1; 方法二（升序）：找当前元素之前，有多少元素的一半比我大 res += mid - i + 1;

方法一：

class Solution {
public:
    int tmp[100005];

    int mergesort(vector<int>& nums, int l, int r)
    {
        if (l >= r) return 0;
        // 1. 根据左右元素划分区间
        int mid = (r + l) >> 1;

        // 2. 计算左右两侧翻转对
        int res = mergesort(nums, l, mid) + mergesort(nums, mid + 1, r);

        // 3. 先计算翻转对数量
        int i = l, j = mid + 1;
        while (i <= mid) //降序的情况
        {
            if (j <= r && nums[j] >= nums[i] / 2.0) j++;
            if (j > r) break;
            res += r - j + 1;
            i++;
        }

        // 4. 合并有序数组
        i = l, j = mid + 1;
        int k = l;
        while (i <= mid && j <= r)
        {
            if (nums[i] <= nums[j]) tmp[k++] = nums[j++];
            else tmp[k++] = nums[i++];
        }

        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= r) tmp[k++] = nums[j++];

        for (j = l; j <= r; j++) nums[j] = tmp[j];
        return res;
    }

    int reversePairs(vector<int>& nums) {
        return mergesort(nums, 0, nums.size() - 1);
    }
};

方法二：

class Solution {
public:
    int tmp[100005];

    int mergesort(vector<int>& nums, int l, int r)
    {
        if (l >= r) return 0;
        // 1. 根据左右元素划分区间
        int mid = (r + l) >> 1;

        // 2. 计算左右两侧翻转对
        int res = mergesort(nums, l, mid) + mergesort(nums, mid + 1, r);

        // 3. 先计算翻转对数量
        int i = l, j = mid + 1;
        while (j <= r) //升序的情况
        {
            while (i <= mid && nums[j] >= nums[i] / 2.0) i++;
            if (i > mid) break;
            res += mid - i + 1;
            j++;
        }

        // 4. 合并有序数组
        i = l, j = mid + 1;
        int k = 0;
        while (i <= mid && j <= r)
        {
            if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
            else tmp[k++] = nums[j++];
        }

        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= r) tmp[k++] = nums[j++];

        for (i = l, j = 0; i <= r; i++, j++) nums[i] = tmp[j];
        return res;
    }

    int reversePairs(vector<int>& nums) {
        return mergesort(nums, 0, nums.size() - 1);
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-09-03，如有侵权请联系 cloudcommunity@tencent.com 删除

排序