Sort_1_mergeSort_归并排序

Algorithm
Created At :
  1. 归并排序
  2. 912.排序数组
  3. 剑指 Offer 51.数组中的逆序对
  4. 315.计算右侧小于当前元素的个数
  5. 493.翻转对
  6. 327.区间和的个数

归并排序

1.归并排序是分治思想, 对于一个长度为 n 的序列, 分解成左边和右边两个长度为 n/2 的序列, 每次递归调用函数使得左右两个子序列有序, 然后将两个序列合并使得整个序列有序. 归并思路框架如下 

void mergeSort(vector<int>& nums, int low, int high) {
  // 处理单个元素的场景
  if (low == high)
    return;
  int mid = low + (r - l) / 2;
  // 递归排序左侧nums[low, mid]
  mergeSort(nums, low, mid);
  // 递归排序右侧nums[mid+1, high]
  mergeSort(nums, mid + 1, high);
  // 合并有序数组nums[l, mid]和有序数组nums[mid+1, high], 利用双指针扫描
  merge(nums, low, mid, high);
}

所有的递归算法, 本质上是在遍历一棵树, 然后在节点上执行逻辑, 归并排序和二叉树的后序遍历是类似的 

void traverse(TreeNode* root) {
  if (root == nullptr) return;
  traverse(root->left);
  traverse(root->right);
  // 后序位置执行逻辑
  cout << root->val; 
  return;
}

合并数组的过程是类似于合并两个有序链表, 双指针维护比较位置, 归并后的数组需要另外开一个数组 tmp 去保存, 然后再将 tmp 复制回原来的数组对应的位置上, 完整的归并排序代码如下: 

vector<int> tmp;
void merge(vector<int>& nums, int low, int high, int mid) {
  int i = low;
  int j = mid + 1;
  int cnt = 0;
  while (i <= mid && j <= high) {
    if (nums[i] <= nums[j]) {
      tmp[cnt++] = nums[i++];
    } else {
      tmp[cnt++] = nums[j++];
    }
  }
  while (i <= mid) {
    tmp[cnt++] = nums[i++];
  }
  while (j <= high) {
    tmp[cnt++] = nums[j++];
  }
  for (int i = 0; i < cnt; ++i) {
    nums[low + i] = tmp[i];
  }  
}
void mergeSort(vector<int>& nums, int low, int high) {
  // 处理单个元素的场景
  if (low >= high)
    return;
  int mid = low + (r - l) / 2;
  // 递归排序左侧的
  mergeSort(nums, low, mid);
  // 递归排序右侧的
  mergeSort(nums, mid + 1, high);
  merge(nums, low, high, mid);
  return;
}

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]

class Solution {
 private:
  vector<int> tmp;
 public:
  void merge(vector<int>& nums, int low, int high, int mid) {
    int i = low;
    int j = mid + 1;
    int cnt = 0;
    while (i <= mid && j <= high) {
      if (nums[i] <= nums[j]) {
        tmp[cnt++] = nums[i++];
      } else {
        tmp[cnt++] = nums[j++];
      }
    }
    while (i <= mid) {
      tmp[cnt++] = nums[i++];
    }
    while (j <= high) {
      tmp[cnt++] = nums[j++];
    }
    for (int k = 0; k < cnt; ++k) {
      nums[low + k] = tmp[k];
    }
  } 
  void mergeSort(vector<int>& nums, int low, int high) {
    if (low >= high) return;
    int mid = low + (high - low) / 2;
    mergeSort(nums, low, mid);
    mergeSort(nums, mid + 1, high);
    merge(nums, low, high, mid);
    return;
  }
  vector<int> sortArray(vector<int>& nums) {
    tmp.resize(nums.size(), 0);
    mergeSort(nums, 0, nums.size() - 1);
    return nums;
  }
};

剑指 Offer 51.数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1: 输入: [7,5,6,4] 输出: 5

分析:
1.归并排序中, 任何合并的过程里面, 我们本质是把任何逆序的元素排成有序的, 例如当前待合并的是
左侧 list=[8,12,16,22,100];
右侧 list=[9,26,55,64,91];

比较过程如下
8 < 9 放入8
12 > 9 放入9 产生了cnt个逆序对(12, 9) (16, 9) (22, 9) (100, 9), cnt = mid - i + 1
12 < 26 放入12
16 < 26 放入16
22 < 26 放入22
100 > 26 放入26 产生了1个逆序对(100, 26) cnt = mid - i + 1
当nums[i] > nums[j]的时候, 算产生的逆序对的个数为 cnt = (mid - i + 1) 个逆序对 

class Solution {
 private:
  vector<int> tmp;
  int ans;
 public:
  void merge(vector<int>& nums, int low, int high, int mid) {
    int i = low;
    int j = mid + 1;
    int cnt = 0;
    while (i <= mid && j <= high) {
      if (nums[i] <= nums[j]) {
        tmp[cnt++] = nums[i++];
      } else {
        ans += mid - i + 1;
        tmp[cnt++] = nums[j++];
      }
    }
    while (i <= mid) {
      tmp[cnt++] = nums[i++];
    }
    while (j <= high) {
      tmp[cnt++] = nums[j++];
    }
    for (int k = 0; k < cnt; ++k) {
      nums[low + k] = tmp[k];
    }
    return;
  }
  void mergeSort(vector<int>& nums, int low, int high) {
    if (low >= high) return;
    int mid = low + (high - low) / 2;
    mergeSort(nums, low, mid);
    mergeSort(nums, mid + 1, high);
    merge(nums, low, high, mid);
    return;
  }
  int reversePairs(vector<int>& nums) {
    tmp.resize(nums.size(), 0);
    ans = 0;
    mergeSort(nums, 0, nums.size()-1);
    return ans;
  }
};

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

给你一个整数数组 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 个更小的元素
示例 2：输入：nums = [-1] 输出：[0]
示例 3：输入：nums = [-1,-1] 输出：[0,0]

分析:
1.要统计所有比x小的元素个数, 需要到采用逆序的归并操作, 为什么这里要用逆序归并而不是顺序的归并呢? 因为只有逆序才能将所有的比x元素小的元素放在右侧的集合
左侧 list=[100,22,16,12,8]
右侧 list=[91,64,55,26,9]

比较过程如下
100>91, 增加cnt个比100小的元素, 然后放入100, cnt = high - j + 1
22<91, 22<55, 22<25, 22>9,
16>9,
12>9, 

class Solution {
 private:
  vector<int> res;
 public:
  void merge(vector<pair<int, int>>& numsWithIdx, int low, int high, int mid) {
    int i = low;
    int j = mid + 1;
    int cnt = 0;
    vector<pair<int, int>> tmp(high - low + 1);
    while (i <= mid && j <= high) {
      if (numsWithIdx[i].first > numsWithIdx[j].first) {
        res[numsWithIdx[i].second] += high - j + 1;
        tmp[cnt++] = numsWithIdx[i++];
      } else {
        tmp[cnt++] = numsWithIdx[j++];
      }
    }
    while (i <= mid) {
      tmp[cnt++] = numsWithIdx[i++];
    }
    while (j <= high) {
      tmp[cnt++] = numsWithIdx[j++];
    }
    for (int k = 0; k < cnt; ++k) {
      numsWithIdx[low + k] = tmp[k];
    }
    return;
  }
  void mergeSort(vector<pair<int, int>>& numsWithIdx, int low, int high) {
    if (low >= high) return;
    int mid = low + (high - low) / 2;
    mergeSort(numsWithIdx, low, mid);
    mergeSort(numsWithIdx, mid + 1, high);
    merge(numsWithIdx, low, high, mid);
    return;
  }
  vector<int> countSmaller(vector<int>& nums) {
    vector<pair<int, int>> numsWithIdx;
    for (int i = 0; i < nums.size(); ++i) {
      numsWithIdx.emplace_back(nums[i], i);
    }
    res.resize(nums.size(), 0);
    mergeSort(numsWithIdx, 0, nums.size()-1);
    return res;
  }
};

493.翻转对

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

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

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

分析:
1.利用归并排序后的结果先统计翻转对的个数, 然后继续归并排序;
左侧 list=[8,12,16,22,100];
右侧 list=[9,26,55,64,91];

8 9
12 9
16 9
22 9
22 26

class Solution {
 private:
  vector<int> tmp;
  int ans;
 public:
  void mergeSort(vector<int>& nums, int low, int high) {
    if (low >= high) return;
    int mid = low + (high - low) / 2;
    mergeSort(nums, low, mid);
    mergeSort(nums, mid + 1, high);

    // 先算翻转对
    int i = low;
    int j = mid + 1;
    while (i <= mid) {
      while (j <= high && (long long) nums[i] > (long long) nums[j] * 2) {
        ++j;
      }
      ans += j - (mid + 1);
      ++i;
    }

    // 再归并
    int p1 = low;
    int p2 = mid + 1;
    int cnt = 0;
    while (p1 <= mid && p2 <= high) {
      if (nums[p1] <= nums[p2]) {
        tmp[cnt++] = nums[p1++];
      } else {
        tmp[cnt++] = nums[p2++];
      }
    }
    while (p1 <= mid) {
      tmp[cnt++] = nums[p1++];
    }
    while (p2 <= high) {
      tmp[cnt++] = nums[p2++];
    }
    for (int k = 0; k < cnt; ++k) {
      nums[low + k] = tmp[k];
    }
    return;
  }
  int reversePairs(vector<int>& nums) {
    tmp.resize(nums.size(), 0);
    ans = 0;
    mergeSort(nums, 0, nums.size()-1);
    return ans;
  }
};

327.区间和的个数

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

示例 1：输入：nums = [-2,5,-1], lower = -2, upper = 2 输出：3 解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。

示例 2：输入：nums = [0], lower = 0, upper = 0 输出：1

分析:
1.区间和首先需要转换一下问题, 给定两个已经升序排列的数组n1, n2, 找出下标 (i,j) 满足 n2(j)-n1(i) 属于 [lower, upper], 这个问题称为 [辅助问题]
2.对于上述问题, 用双指针的方法可以实现, 维护n2的两个指针l和r, l和r都指向n2的第一个元素
3.只考察 n1 的第1个元素, 移动 n2 的 l 指针直到 n2[l] >= n1[0] + lower, 然后 l 指针后面的所有元素均满足 >= n1[0] + lower; l 停下来不动, 再动r, 直到 n2[r] > n1[0] + upper, 然后 r 左边的元素全部满足 <= n1[0] + upper, 然后区间[l, r)内所有的下标 j 都满足 n2[j] - n1[0] 属于 [lower, upper] 区间
4.然后考察 n1 的第2个元素, 移动方法同上; 然后考察 n1 的第 3 个元素…; 最终我们统计到所有满足条件的下标对的数量
5.考察 [辅助问题] 和 [原问题] 之间的关系, 采用归并排序的方式, 得到两个数组排序后的形式以及对应的下标对的数量; 对于原数组而言, 若要找出全部的下标对的数量, 需要再额外找出做左端点在左侧数组, 右端点在右侧数组的下标对数量
6.计算区间之和的时候用前缀和数组的技巧, 回顾下 preSum 这个数组构建是 

preSum[0] = 0  
preSum[1] = nums[0]
preSum[2] = nums[0] + nums[1]
preSum[3] = nums[0] + nums[1] + nums[2]
preSum[4] = nums[0] + nums[1] + nums[2] + nums[3]
preSum[n] = nums[0] + .. + nums[n-1]
sumRange(1, 3) = preSum(4) - preSum(1) = nums[1] + nums[2] + nums[3]
sumRange(i, j) = preSum(j+1, i)

class Solution {
 public:
  int mergeSortCount(vector<long>& sum, int low, int high, int lower, int upper) {
    if (low >= high) {
      return 0;
    }
    int mid = low + (high - low) / 2;
    int leftCnt = mergeSortCount(sum, low, mid, lower, upper);
    int rightCnt = mergeSortCount(sum, mid+1, high, lower, upper);
    int ret = leftCnt + rightCnt;

    int i = low;
    int l = mid + 1;
    int r = mid + 1; 
    while (i <= mid) {
      while (l <= high && sum[l] - sum[i] < lower) ++l;
      while (r <= high && sum[r] - sum[i] <= upper) ++r;
      ret += (r - l);
      ++i;
    }

    vector<long> tmp(high - low + 1);
    int p1 = low;
    int p2 = mid + 1;
    int cnt = 0;
    while (p1 <= mid && p2 <= high) {
      if (sum[p1] <= sum[p2]) {
        tmp[cnt++] = sum[p1++];
      } else {
        tmp[cnt++] = sum[p2++];
      }
    }
    while (p1 <= mid) {
      tmp[cnt++] = sum[p1++];
    }
    while (p2 <= high) {
      tmp[cnt++] = sum[p2++];
    }
    for (int k = 0; k < cnt; ++k) {
      sum[low + k] = tmp[k];
    }
    return ret;
  }
  int countRangeSum(vector<int>& nums, int lower, int upper) {
    long sum = 0;
    vector<long> preSum{0};
    for (auto& ele: nums) {
      sum += ele;
      preSum.emplace_back(sum);
    }
    return mergeSortCount(preSum, 0, preSum.size()-1, lower, upper);
  }
};
转载请注明来源, from goldandrabbit.github.io

💰

©2018-2024

Built with Hexo and 3-hexo theme

×

Help us with donation