暑期算法训练.10

发布于：2025-07-30 ⋅ 阅读:(21) ⋅ 点赞:(0)

目录

力扣 47.912 排序数组

47.1 题目解析：

47.2 算法思路：

​编辑 

47.3 代码演示：

​编辑

47.4 总结反思：

力扣 48.LCR 170交易逆序对的总数

48.1 题目解析：

48.2 算法思路：

48.3 代码演示：

48.4 总结反思：

49. 力扣 315 计算右侧小于当前元素的个数

49.1 题目解析：

49.2 算法思路：

49.3 代码演示：

​编辑

49.4 总结反思：

50. 力扣 493 翻转对

50.1 题目解析：

​编辑 

50.2 算法思路：

​编辑 

50.3 代码演示：

关键差别：条件与排序顺序的不一致性

50.4 总结反思：

 

 

今天的题目属实是把我做的恶心了。那么下面就跟作者一起来看一下吧

力扣 47.912 排序数组

47.1 题目解析：

这道题目咱们上一期讲过，但是呢，咱们上一期使用的是快速排序算法，但是咱们今天要使用归并算法。

47.2 算法思路：

 

当只剩下一个元素的时候，往上一层回溯，合并两个有序的数组。其实这个算法也挺简单的。主要是看代码进行分析，待会咱们主要的看代码进行分析。

而且咱们会发现归并排序是先把左边搞好，再把右边搞好，最后再合并到中间。类似于后序遍历。而快速排序类似于前序遍历。

47.3 代码演示：

vector<int> tmp;//将tmp设置为全局变量，避免了反复的创建临时变量带来的消耗
void mergeSort(vector<int>& nums, int left, int right);

vector<int> sortArray(vector<int>& nums)
{
    tmp.resize(nums.size());// 调整临时数组大小与输入数组相同，为归并操作准备空间
    mergeSort(nums, 0, nums.size() - 1);//这个传的是下标

    return nums;// 返回排序后的数组（原数组已被修改）
}
void mergeSort(vector<int>& nums, int left, int right)
{
    if (left >= right) return;//为结束归并排序做准备
    // 1. 选择中间点划分区间

        int mid = (left + right) >> 1; /* 等价于(left + right) / 2，位运算效率更高*/
    // [left, mid] [mid + 1, right]
    // 2. 把左右区间排序

        mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    // 3. 合并两个有序数组
        //left与right的位置你不需要担心，每次都是设置好的，就比如合并到一个大数组里面的时候，这个left与right就是对应的大数组的left与right
        int cur1 = left, cur2 = mid + 1, i = 0; //临时数组(tmp)索引（从0开始填充）,由于每次虽然说递归的时候，原数组中的每个下标会随着递归而变化，
        //但是你每次的临时数组的起始下标是不变的
        while (cur1 <= mid && cur2 <= right) // 双指针遍历两个区间，选择较小元素放入tmp
        tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] :// 稳定排序(即等于的时候）：相等时取左区间元素
        nums[cur2++];
    // 处理没有遍历完的数组
         // 处理左区间剩余元素
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        // 处理右区间剩余元素
        while (cur2 <= right) tmp[i++] = nums[cur2++];
    // 4. 还原
         // 4. 将临时数组数据复制回原数组
        for (int i = left; i <= right; i++)
            nums[i] = tmp[i - left];
}
int main()
{
    vector<int>  nums =   { 5,2,3,1 };
    vector<int> outcome = sortArray(nums);
    for (auto& e : outcome)
    {
        cout << e << "";
    }
    cout << endl;
    return 0;
}

这里也用到了递归，需要注意的是，如果上面的i定义的从0开始，那么下面将临时数组中的元素回归到原数组，就得是从i-left开始，因为这样的话，才是从下标从0开始。但要是i定义的left，那么只需要tmp[left]即可。不需要i-left。

其实也就是1.选择中间点划分区间

2.把左右区间排序

3.合并两个有序数组

4. 最后将临时复制到原数组中即可。

47.4 总结反思：

归并排序是做后面题目的基础，大家还是搞定归并排序再来看后面的题目，

力扣 48.LCR 170交易逆序对的总数

48.1 题目解析：

题目很短，i<j,但是nums[i]>nums[j]，前一个数比后一个数大即可。

48.2 算法思路：

这道题目其实挺复杂的。

解法一：咱们如果说使用暴力解法的话，就是两层for循环，那么一定会超时的。所以咱们选择使用另外一种解法：

解法二：

就是左半部分挑出来的逆序对数量加上右半部分挑出来的逆序对数量再加上一左一右各挑出一个组成逆序对的数量就是咱们所求的逆序对的数量。

那么类比于咱们的归并排序：

咱们可以改进一下： 就是左半部分挑出来的逆序对数量（挑完后，排序）加上右半部分挑出来的逆序对数量（挑完后，排序）再加上一左一右各挑出一个组成逆序对的数量（这个是不管前面的排序的，例如：固定左半部分的一个数，只找右半部份比左半部分那个数小的数即可。你有没有顺序都是不影响我的），就是咱们所求的逆序对的数量。

那么这个逆序对是在合并两个有序序列的时候求的。方法有两种，但是只能在不同的场合下使用：

1.升序（只可用快速统计出某个数前面有多少个数比它大的方法）以右边的数组为基准

给定left=[5,7,9],right=[4,5,8].辅助数组help=[],cur1遍历left数组，cur2遍历right数组，ret记录逆序对的数量。

循环一：left[cur]>right[cur2],由于数组升序，说明left的[cur1,2]这几个数都比right[cur2]这一个数大，那么ret+=2-cur1+1。而将cur2放入辅助数组中（谁小谁先进辅助数组，因为这个是升序）。辅助数组就是排序的时候用的，（合并为一个大数组）。cur2++遍历下一个元素。此时left[5,7,9]，right=[x,5,8]，help=[4]，ret=3，cur1=0，cur2=1.

循环二：left[cur1]=right[cur2]，此时没有逆序对，将left[cur1]先进入到辅助数组中，若去的是right的5，会导致错过7，5，以及9，5.

循环三：left[cur1]>right[cur2],此时，left中的[cur1,2]，的均比right[cur2]的大，此时ret+=2.right[cur2]放入辅助数组中，cur2++，此时left[x,7,9].right[x,x,8]。help[4,9,5]。ret=5，cur1=1，cur2=2.

循环四：left[cur1]<right[cur2]，此时不构成逆序对，left[cur1]放入help中，cur1++

循环五：left[cur1]>right[cur2],此时left中只剩下一个可与right[cur2]构成逆序对，那么更新ret，并让cur2++，此时cur2已经越界了。

那么剩余元素：只要是剩下的都是大元素了。

1.若左边剩余元素：左边的元素大于右边的，但是由于右边的元素已经全部计算过了。所以ret不更新。仅排序。

2.若右边剩余元素：右边的元素大于左边的，但不符合逆序对的定义，所以仅排序。

此时，在合并有序数组的时候，若遇到左数组元素大于右数组当前元素，可计算左数组中剩余元素的长度，可快速的求出右数组当前元素前面有多少个比它大。（这种有序数组可比一个一个的枚举快多了）。

那么此时可以总结一下了：若nums[cur1]<=nums[cur2],cur1++

若nums[cur1]>nums[cur2],ret+=mid-cur1+1,cur2++

OK，到目前为止，第一种方法总算讲完了，还有第二种方法：

2.降序（统计某个数后面有多少个数比它小），以左数组为基准

降序只可以用这个方法，那么原理同上，我就不做这么详细的介绍了，我只进行一下总结：

 

那么1.nums[cur1]>nums[cur2],那么right的[cur2,right]都比left[cur1]小，此时ret+=right-cur2+1，cur1++

2.nums[cur1]==nums[cur2],此时cur2++

3.nums[cur1]<nums[cur2],cur2++

而降序是谁大，谁先进辅助数组。

但其实以上这两种方法，都可以通过力扣这道题目的测试。

48.3 代码演示：

方法一：升序：

 //升序策略1，并且这个是计算逆序对的时候，同时合并数组
 int tmp[50010];
 int mergeSort(vector<int>& nums, int left, int right);
 int reversePairs(vector<int>& nums)
 {
     return mergeSort(nums, 0, nums.size() - 1);
 }
 int mergeSort(vector<int>& nums, int left, int right)
 {
     if (left >= right) return 0;
     int ret = 0;
     // 1. 找中间点，将数组分成两部分

     int mid = (left + right) >> 1;
     // [left, mid][mid + 1, right]
     // 2. 左边的个数+排序+右边的个数+排序

     ret += mergeSort(nums, left, mid);
     ret += mergeSort(nums, mid + 1, right);
     // 3.⼀左⼀右的个数

     int cur1 = left, cur2 = mid + 1, i = 0;
     while (cur1 <= mid && cur2 <= right) // 升序的时候

     {
         if (nums[cur1] <= nums[cur2])
         {
             tmp[i++] = nums[cur1++]; // 不构成逆序对
         }
         else
         {
             ret += mid - cur1 + 1;   // 统计逆序对
             tmp[i++] = nums[cur2++];
         }
     }
     // 4. 处理⼀下排序

     while (cur1 <= mid) tmp[i++] = nums[cur1++];
     while (cur2 <= right) tmp[i++] = nums[cur2++];
     for (int j = left; j <= right; j++)
         nums[j] = tmp[j - left];

     return ret;
 }
 int main()
 {
     vector<int> nums = { 5,4,3,2,1 };
     cout << reversePairs(nums) << endl;

     return 0;
 }

方法二:降序

//降序策略2
int tmp[50010];
int mergeSort(vector<int>& nums, int left, int right);
int reversePairs(vector<int>& nums)
{
    return mergeSort(nums, 0, nums.size() - 1);
}
int mergeSort(vector<int>& nums, int left, int right)
{
    if (left >= right) return 0;
    int ret = 0;
    // 1. 找中间点，将数组分成两部分

    int mid = (left + right) >> 1;
    // [left, mid][mid + 1, right]
    // 2. 左边的个数+排序+右边的个数+排序

    ret += mergeSort(nums, left, mid);
    ret += mergeSort(nums, mid + 1, right);
    // 3.⼀左⼀右的个数

    int cur1 = left, cur2 = mid + 1, i = 0;
    while (cur1 <= mid && cur2 <= right) // 升序的时候

    {
        if (nums[cur1] <= nums[cur2])
        {
            tmp[i++] = nums[cur2++]; // 不构成逆序对
        }
        else
        {
            ret += right-cur2+1;   // 统计逆序对
            tmp[i++] = nums[cur1++];
        }
    }
    // 4. 处理⼀下排序

    while (cur1 <= mid) tmp[i++] = nums[cur1++];
    while (cur2 <= right) tmp[i++] = nums[cur2++];
    for (int j = left; j <= right; j++)
        nums[j] = tmp[j - left];

    return ret;
}
int main()
{
    vector<int> nums = { 5,4,3,2,1 };
    cout << reversePairs(nums) << endl;

    return 0;
}

其实这题是可以分为，计算逆序对，之后再合并数组，但为什么计算与合并同时进行，这个咱们后面讲

48.4 总结反思：

本题还是有难度的，并且有参考价值，大家还是得好好的参悟一下

49. 力扣 315 计算右侧小于当前元素的个数

49.1 题目解析：

本题还是有难度的，我感觉今天的题全都有难度，毕竟是三道hard题目。这道题目大家仔细阅读，还是可以看出来门道的。

49.2 算法思路：

那么咱们直接进入算法讲解，这道题目虽然是用归并排序做的，但是细节比较多。下面听我仔细的讲解一下：

这个需要用到上一道题的方法二（就是降序），即

nums[cur1]<=nums[cur2],cur2++.

nums[cur1]>nums[cur2],nums[cur1]对应的那个下标的那个里面再写上ret+=right-cur2+1。

所以，本题重要的绑定下标：

这个ret，最后返回的是ret，所以这个ret应该是与index一样大的数组，且下标也一样，才能用来存储对应的那个数的右侧小于它的个数，这里还得是+=，因为这里是递归，所以不知加一次，可能递归后还得加。且是ret[index[cur1]],直到cur1越界。

由于咱们有了两个数组，nums，index，故还得有两个临时数组，来存储归并后的东西。

例如，nums的tmpNums就是用来暂存归并后的数值，最后再归还

而index的tmpIndex为暂存归并后的索引。且这个索引的顺序与数值的顺序是一致的。所以不用担心归并后的数值与下标不对应。

例如，先暂存2，那么2的下标为1，（index[1])

所以归并后，即使2在第一个，但下标仍是1，而不是0.

因为index与nums是一一对应的，所以说他俩的下标也是对应的，所以比如cur2为3，那么数值为3的下标就是3，这个下标3就是cur2对应的那个数字（有点别扭，但是要理解）

49.3 代码演示：

 右侧小于当前元素的个数
vector<int> ret; // 存储结果
vector<int> index; // 记录nums中当前元素的原始下标

int tmpNums[500010];// 临时存储归并后的数值
int tmpIndex[500010]; // 临时存储归并后的索引
void mergeSort(vector<int>& nums, int left, int right);
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;
}

void mergeSort(vector<int>& nums, int left, int right)//⽆需返回值，因为直接对全局变量修改，当函数结束的时候，全局变量已经被修改成最后的结果。
{
    if (left >= right) return;
    // 1. 根据中间元素，划分区间

        int mid = (left + right) >> 1;
    // [left, mid]  [mid + 1, right]
    // 2. 先处理左右两部分

        mergeSort(nums, left, mid);
    mergeSort(nums, mid + 1, right);
    // 3. 处理⼀左⼀右的情况

        int cur1 = left, cur2 = mid + 1, i = 0;
    while (cur1 <= mid && cur2 <= right) // 降序

    {
        if (nums[cur1] <= nums[cur2])
        {
            tmpNums[i] = nums[cur2];
            tmpIndex[i++] = index[cur2++];
        }
        else
        {
            ret[index[cur1]] += right - cur2 + 1; // 重点
            //需要累加到ret数组的index[cur1]位置上（因为index存储的是元素对应位置在原数组中的下标）

                tmpNums[i] = nums[cur1];
                tmpIndex[i++] = index[cur1++];
            }
    }
        // 4. 处理剩下的排序过程

        while (cur1 <= mid)
        {
            tmpNums[i] = nums[cur1];
            tmpIndex[i++] = index[cur1++];
        }
    while (cur2 <= right)
    {
        tmpNums[i] = nums[cur2];
        tmpIndex[i++] = index[cur2++];
    }
    for (int j = left; j <= right; j++)
    {
        nums[j] = tmpNums[j - left];
        index[j] = tmpIndex[j - left];
    }
}
int main()
{
    vector<int> nums = { 5,2,6,1 };
    vector<int> outcome = countSmaller(nums);
    for (auto& e : outcome)
    {
        cout << e << "";
    }
    cout << endl;
    return 0;
}

代码量不少

49.4 总结反思：

这道题目还是很不错的，大家要仔细的理解一下

50. 力扣 493 翻转对

50.1 题目解析：

 

这道题目大家看着是不是与那个逆序对的题目很像？没错，就是很像，以至于解法都一模一样。只不过这个是i<j,nums[i]>2*nums[j]

50.2 算法思路：

 

策略一：计算当前元素后面有多少元素的两倍比我小（降序）。以cur1为基准。

当出现left[cur1]>2*right[cur2]时，此时cur1++，此时ret+=right-cur2+1.相反，left[cur1]<=2*right[cur2],(即left[cur1]/2.0<=right[cur2])。cur2++

 

策略二：计算当前元素之前，有多少元素的一半比我大（升序），以cur2为基准

当出现left[cur1]>2*right[cur2],此时ret+=mid-cur1+1.此时cur2++。反之：cur1++

基准不同，while循环里的条件也不同。

50.3 代码演示：

策略一：降序

//降序的数组
    int tmp[50010];
    int mergeSort(vector<int>& nums, int left, int right);
    int reversePairs(vector<int>& nums)
    {
        return mergeSort(nums, 0, nums.size() - 1);
    }
    int mergeSort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return 0;
        int ret = 0;
        // 1. 先根据中间元素划分区间

            int mid = (left + right) >> 1;
        // [left, mid] [mid + 1, right]
        // 2. 先计算左右两侧的翻转对

            ret += mergeSort(nums, left, mid);
        ret += mergeSort(nums, mid + 1, right);
        // 3. 先计算翻转对的数量

            int cur1 = left, cur2 = mid + 1, i = 0;
        while (cur1 <= mid) // 降序的情况
        {
            while (cur2 <= right && nums[cur2] >= nums[cur1] /2.0) //乘法可能会溢出，所以改为除法
                cur2++;
            if (cur2 > right)
                break;
            ret += right - cur2 + 1;
            cur1++;
        }
        // 4. 合并两个有序数组

            cur1 = left, cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right)
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];//大的先进
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];
        for (int j = left; j <= right; j++)
            nums[j] = tmp[j-left];

        return ret;
    }
    int main()
    {
        vector<int> nums = { 1,3,2,3,1 };
        cout << reversePairs(nums) << endl;
        return 0;
    }

策略二：升序

//升序的数组
int tmp[50010];
int mergeSort(vector<int>& nums, int left, int right);
int reversePairs(vector<int>& nums)
{
    return mergeSort(nums, 0, nums.size() - 1);
}
int mergeSort(vector<int>& nums, int left, int right)
{
    if (left >= right) return 0;
    int ret = 0;
    // 1. 先根据中间元素划分区间

    int mid = (left + right) >> 1;
    // [left, mid] [mid + 1, right]
    // 2. 先计算左右两侧的翻转对

    ret += mergeSort(nums, left, mid);
    ret += mergeSort(nums, mid + 1, right);
    // 3. 先计算翻转对的数量

    int cur1 = left, cur2 = mid + 1, i = 0;
    while (cur2 <= right) // 升序的情况

    {
        while (cur1 <= mid && nums[cur2] >= nums[cur1] / 2.0)//乘法可能会溢出，所以改为除法
            cur1++;
        if (cur1 > mid)
            break;
        ret += mid - cur1 + 1;
        cur2++;
    }
    // 4. 合并两个有序数组

    cur1 = left, cur2 = mid + 1;
    while (cur1 <= mid && cur2 <= right)
        tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];//小的先进
    while (cur1 <= mid)
        tmp[i++] = nums[cur1++];
    while (cur2 <= right)
        tmp[i++] = nums[cur2++];
    for (int j = left; j <= right; j++)
        nums[j] = tmp[j - left];

    return ret;
}
int main()
{
    vector<int> nums = { 1,3,2,3,1 };
    cout << reversePairs(nums) << endl;
    return 0;
}

可以发现，不管是升序还是降序，都是计算与合并分开。但是那个逆序对的题，为什么计算与合并是放一起的呢？

原因：

在归并排序中，数组被递归地分成两半，分别排序后合并。合并过程中，由于两个子数组都是有序的（升序），我们可以高效地计算跨越两半的逆序对（即左半元素 vs 右半元素）。

  • 合并与计数同时进行的原理：

    • 在合并两个有序子数组（左数组 L 和右数组 R）时，我们使用两个指针 i（左数组索引）和 j（右数组索引）。

    • 当 L[i] > R[j] 时，由于左数组和右数组都是升序，L[i] 不仅大于 R[j]，还大于右数组中所有剩余元素（即从 j 到末尾的所有元素），因为这些元素都大于等于 R[j]。

    • 因此，此时可以一次性添加多个逆序对：数量 = 右数组剩余元素个数（len(R) - j）。

    • 然后，我们将 R[j] 添加到合并数组，并移动指针。

    • 关键点：条件 nums[i] > nums[j] 直接与合并时的比较操作（L[i] > R[j]）一致，所以计数可以嵌入合并循环中，无需额外步骤。

  • 示例步骤（record = [9,7,5,4,6]）：
    假设归并排序过程中，左数组 L = [5,7,9]（排序后），右数组 R = [4,6]（排序后）。合并时：

    • 比较 L[0]=5 和 R[0]=4：5 > 4，所以 5 与 R[0]=4 和所有右剩余元素（R[1]=6）构成逆序对？不，5>4 是逆序，但 5<6 不是。实际在合并中：

      • 当取 R[j] 时，如果 L[i] > R[j]，则 L[i] 及左剩余所有元素都大于 R[j]（因为左数组有序），但这里只针对当前 i。
        标准做法：

      • 初始化逆序对计数 = 0。

      • i=0, j=0：L[0]=5 > R[0]=4，所以添加右剩余元素数（此时右数组有 2 个元素，但只针对当前 j，计数 += 1（因为 R[j] 被比较），然后取 R[0] 到合并数组，j++。

      • 现在 i=0, j=1：L[0]=5 <= R[1]=6，取 L[0] 到合并数组，i++。

      • i=1, j=1：L[1]=7 > R[1]=6，添加右剩余元素数（len(R) - j = 1），计数 +=1，取 R[1]，j++。

      • 等等。实际总跨越逆序对需累计。
        详细过程略，但重点是：在合并循环中，通过简单比较 L[i] > R[j]，就能立即得到逆序对信息，并继续合并。

  • 为什么有效：

    • 条件 nums[i] > nums[j] 与合并时的值比较完全匹配。

    • 合并步骤的 O(n) 时间内，既能完成数组合并，又能计算跨越逆序对，无需额外开销。

    • 总时间复杂度 O(n log n)，空间复杂度 O(n)。

 

为什么翻转对不可以合并？ 

  • 合并时，我们比较 L[i] 和 R[j] 来决定哪个元素添加到合并数组（基于值的大小），但翻转对的条件涉及 2 * R[j]，这破坏了与合并比较操作的一致性。

  • 具体来说：

    • L[i] > R[j] 并不意味着 L[i] > 2 * R[j]（例如，L[i]=4, R[j]=3，则 4>3 但 4 < 2*3=6，不满足翻转对）。

    • 反之，L[i] <= R[j] 也不意味着 L[i] <= 2 * R[j]（例如，L[i]=3, R[j]=2，则 3>2 但 3 > 2*2=4？假，3<4）。

  • 因此，在合并循环中，当比较 L[i] 和 R[j] 时，我们无法直接推断 L[i] > 2 * R[j] 是否成立，也不能像简单逆序对那样批量添加多个翻转对。

关键差别：条件与排序顺序的不一致性

  • 在简单逆序对中，数组按值排序（升序）后，索引关系（i < j 对应左半 vs 右半）和值关系（nums[i] > nums[j]）在合并时可以通过指针直接捕获。

  • 在重要翻转对中，条件 nums[i] > 2 * nums[j] 引入了非线性因子（2），使得：

    • 排序后的值顺序（L 和 R 升序）不能直接用于判断 L[i] > 2 * R[j]，因为 2 * R[j] 改变了值的尺度。

    • 例如，右数组 R 是升序，但 2 * R 也是升序（如果元素非负），但合并比较的是 L[i] vs R[j]，而不是 L[i] vs 2 * R[j]。

 

总的来说就是逆序对的判断条件与合并条件一致。而翻转对的不一致。

50.4 总结反思：

今天的题量挺少的，但是知识量很大，所以大家仔细的研读一下....

本篇完......

 

 

 

 

 

 

 

 

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布