devbox
编程挑战者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【LeetCode】排序精选12题

作者：编程挑战者 | 2024-02-05 16:38:55

赞

踩

【LeetCode】排序精选12题

目录

排序：

1. 合并区间（中等）

2. 数组的相对排序（简单）

快速排序：

1. 颜色分类（中等）

2. 排序数组（中等）

3. 数组中的第K个最大元素（中等）

4. 最小K个数（中等）

归并排序：

1. 排序数组（中等）

2. 交易逆序对的总数（困难）

3. 计算右侧小于当前元素的个数（困难）

4. 翻转对（困难）

5. 排序链表（中等）

6. 合并 K 个升序链表（困难）

6.1 递归解法（归并）

6.2 迭代解法（堆）

排序：

1. 合并区间（中等）

先将所有区间按照起始位置排序。如果当前区间的起始位置 <= 前一个区间的结束位置，则可以合并，前一个区间不变，当前区间变为合并后的区间。如果当前区间和前一个区间不能合并，则把前一个区间加到答案中。遍历完成后，还要把最后一个区间加到答案中。

  1. class Solution {
  2. public:
  3.     vector<vector<int>> merge(vector<vector<int>>& intervals) {
  4.         int n = intervals.size();
  5.         sort(intervals.begin(), intervals.end());
  6.         vector<vector<int>> ans;
  7.         for (int i = 1; i < n; i++)
  8.         {
  9.             if (intervals[i][0] <= intervals[i - 1][1])
  10.             {
  11.                 // 合并
  12.                 intervals[i][0] = min(intervals[i][0], intervals[i - 1][0]);
  13.                 intervals[i][1] = max(intervals[i][1], intervals[i - 1][1]);
  14.             }
  15.             else
  16.             {
  17.                 ans.push_back(intervals[i - 1]);
  18.             }
  19.         }
  20.         ans.push_back(intervals[n - 1]);
  21.         return ans;
  22.     }
  23. };

2. 数组的相对排序（简单）

对于arr1的两个元素：

  • 如果都在arr2中，按下标进行比较，下标小的靠前
  • 如果一个在arr2中，一个不在arr2中，在arr2中的靠前
  • 如果都不在arr2中，直接比较两个元素的大小即可

使用哈希表记录arr2中的元素，key——arr2中的某元素，value——该元素对应的下标。

使用sort函数搭配lambda表达式实现自定义排序。

  1. class Solution {
  2. public:
  3.     vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
  4.         unordered_map<int, int> hash;
  5.         // 初始化哈希表
  6.         for (int i = 0; i < arr2.size(); i++)
  7.         {
  8.             hash[arr2[i]] = i;
  9.         }
  10.         // 自定义排序
  11.         sort(arr1.begin(), arr1.end(), [&](int e1, int e2)
  12.         {
  13.             if (hash.count(e1) && hash.count(e2))
  14.                 return hash[e1] < hash[e2];
  15.             else if (hash.count(e1))
  16.                 return true;
  17.             else if (hash.count(e2))
  18.                 return false;
  19.             else
  20.                 return e1 < e2;
  21.         });
  22.         return arr1;
  23.     }
  24. };

快速排序：

1. 颜色分类（中等）

类比移动零：

得出数组分三块的示意图：

  • left指向0序列的最后一个，因此初始化为-1
  • i用来扫描数组，因此初始化为0
  • right指向2序列的第一个，因此初始化为n
  1. class Solution {
  2. public:
  3.     void sortColors(vector<int>& nums) {
  4.         int n = nums.size();
  5.         int left = -1;
  6.         int right = n;
  7.         int i = 0;
  8.         while (i < right)
  9.         {
  10.             if (nums[i] == 0)
  11.             {
  12.                 swap(nums[++left], nums[i++]);
  13.             }
  14.             else if (nums[i] == 1)
  15.             {
  16.                 i++;
  17.             }
  18.             else
  19.             {
  20.                 swap(nums[--right], nums[i]);
  21.             }
  22.         }
  23.     }
  24. };

2. 排序数组（中等）

普通快排会超时，必须优化，可以使用数组划分三块的思想搭配随机选择基准元素的方法。

在待排序表中随机取一个元素key作为基准值，通过一趟排序将待排序表划分为独立的三部分区间[0, left]，区间[left + 1, right - 1]，区间[right, n - 1]，使得区间[0, left]中的所有元素小于key，区间[left + 1, right - 1]中的所有元素等于key，区间[right, n - 1]中的所有元素大于key，则等于key的元素都放在了其最终位置——区间[left + 1, right - 1]上，这个过程称为一次划分。然后分别递归地对两个没排好序的子表重复上述过程，直至每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

  1. class Solution {
  2. public:
  3.     vector<int> sortArray(vector<int>& nums) {
  4.         srand((unsigned int)time(nullptr)); // 设置随机数种子
  5.         quickSort(nums, 0, nums.size() - 1);
  6.         return nums;
  7.     }
  8.  
  9. private:
  10.     void quickSort(vector<int>& nums, int begin, int end)
  11.     {
  12.         // 递归出口
  13.         if (begin >= end)
  14.             return;
  15.         // 划分左中右三个子区间
  16.         vector<int> ret = partition(nums, begin, end);
  17.         int left = ret[0];
  18.         int right = ret[1]; 
  19.         // 递归排序左右两个子区间
  20.         quickSort(nums, begin, left);
  21.         quickSort(nums, right, end);
  22.     }
  23.     vector<int> partition(vector<int>& nums, int begin, int end)
  24.     {
  25.         // 随机取key
  26.         int key = nums[rand() % (end - begin + 1) + begin];
  27.         // 数组分三块
  28.         int left = begin - 1;
  29.         int right = end + 1;
  30.         int i = begin;
  31.         while (i < right)
  32.         {
  33.             if (nums[i] < key)
  34.             {
  35.                 swap(nums[++left], nums[i++]);
  36.             }
  37.             else if (nums[i] == key)
  38.             {
  39.                 i++;
  40.             }
  41.             else
  42.             {
  43.                 swap(nums[--right], nums[i]);
  44.             }
  45.         }
  46.         return { left,right };
  47.     }
  48. };

3. 数组中的第K个最大元素（中等）

快速选择算法是基于快速排序算法思想的用于解决Top-K问题的算法，时间复杂度为O(n)。

在快排中，当我们把数组分成三块之后：[begin, left]，[left + 1, right - 1]，[right, end]，我们可以通过计算每一个区间内元素的个数，进而推断出我们要找的元素是在哪一个区间里面。

  1. class Solution {
  2. public:
  3.     int findKthLargest(vector<int>& nums, int k) {
  4.         srand((unsigned int)time(nullptr)); // 设置随机数种子
  5.         return quickSelect(nums, 0, nums.size() - 1, k);
  6.     }
  7.  
  8. private:
  9.     int quickSelect(vector<int>& nums, int begin, int end, int k)
  10.     {
  11.         // 递归出口
  12.         if (begin == end)
  13.             return nums[begin];
  14.         // 划分左中右三个子区间
  15.         vector<int> ret = partition(nums, begin, end);
  16.         int left = ret[0];
  17.         int right = ret[1]; 
  18.         int key = ret[2];
  19.         // 分类讨论
  20.         int c = end - right + 1;
  21.         int b = right - left - 1;
  22.         if (c >= k)
  23.             return quickSelect(nums, right, end, k);
  24.         else if (b + c >= k)
  25.             return key;
  26.         else
  27.             return quickSelect(nums, begin, left, k - b - c);
  28.     }
  29.     vector<int> partition(vector<int>& nums, int begin, int end)
  30.     {
  31.         // 随机取key
  32.         int key = nums[rand() % (end - begin + 1) + begin];
  33.         // 数组分三块
  34.         int left = begin - 1;
  35.         int right = end + 1;
  36.         int i = begin;
  37.         while (i < right)
  38.         {
  39.             if (nums[i] < key)
  40.             {
  41.                 swap(nums[++left], nums[i++]);
  42.             }
  43.             else if (nums[i] == key)
  44.             {
  45.                 i++;
  46.             }
  47.             else
  48.             {
  49.                 swap(nums[--right], nums[i]);
  50.             }
  51.         }
  52.         return { left,right,key };
  53.     }
  54. };

4. 最小K个数（中等）

和上一题“数组中的第K个最大元素”类似。

  1. class Solution {
  2. public:
  3.     vector<int> smallestK(vector<int>& arr, int k) {
  4.         srand((unsigned int)time(nullptr)); // 设置随机数种子
  5.         quickSelect(arr, 0, arr.size() - 1, k);
  6.         return { arr.begin(),arr.begin() + k };
  7.     }
  8.  
  9. private:
  10.     void quickSelect(vector<int>& nums, int begin, int end, int k)
  11.     {
  12.         // 递归出口
  13.         if (begin >= end)
  14.             return;
  15.         // 划分左中右三个子区间
  16.         vector<int> ret = partition(nums, begin, end);
  17.         int left = ret[0];
  18.         int right = ret[1]; 
  19.         // 分类讨论
  20.         int a = left - begin + 1;
  21.         int b = right - left - 1;
  22.         if (a > k)
  23.             quickSelect(nums, begin, left, k);
  24.         else if (a + b >= k)
  25.             return;
  26.         else
  27.             quickSelect(nums, right, end, k - a - b);
  28.     }
  29.     vector<int> partition(vector<int>& nums, int begin, int end)
  30.     {
  31.         // 随机取key
  32.         int key = nums[rand() % (end - begin + 1) + begin];
  33.         // 数组分三块
  34.         int left = begin - 1;
  35.         int right = end + 1;
  36.         int i = begin;
  37.         while (i < right)
  38.         {
  39.             if (nums[i] < key)
  40.             {
  41.                 swap(nums[++left], nums[i++]);
  42.             }
  43.             else if (nums[i] == key)
  44.             {
  45.                 i++;
  46.             }
  47.             else
  48.             {
  49.                 swap(nums[--right], nums[i]);
  50.             }
  51.         }
  52.         return { left,right };
  53.     }
  54. };

归并排序：

1. 排序数组（中等）

归并排序的基本思想是基于分治法的：将两个有序表合并成一个新的有序表，这种两两归并的排序方法称为2路归并排序。

  1. class Solution {
  2. public:
  3.     vector<int> sortArray(vector<int>& nums) {
  4.         mergeSort(nums, 0, nums.size() - 1);
  5.         return nums;
  6.     }
  7.  
  8. private:
  9.     void mergeSort(vector<int>& nums, int begin, int end)
  10.     {
  11.         // 递归出口
  12.         if (begin >= end)
  13.             return;
  14.         // 划分左右两个子区间
  15.         int mid = (begin + end) / 2;
  16.         // 递归排序两个子区间
  17.         mergeSort(nums, begin, mid);
  18.         mergeSort(nums, mid + 1, end);
  19.         // 合并两个有序子区间
  20.         merge(nums, begin, mid, end);
  21.     }
  22.     void merge(vector<int>& nums, int begin, int mid, int end)
  23.     {
  24.         int n = end - begin + 1;
  25.         vector<int> tmp(n);
  26.         int begin1 = begin, end1 = mid;
  27.         int begin2 = mid + 1, end2 = end;
  28.         int i = 0;
  29.  
  30.         // 升序排序
  31.         while (begin1 <= end1 && begin2 <= end2)
  32.         {
  33.             if (nums[begin1] < nums[begin2])
  34.             {
  35.                 tmp[i++] = nums[begin1++];
  36.             }
  37.             else
  38.             {
  39.                 tmp[i++] = nums[begin2++];
  40.             }
  41.         }
  42.         while (begin1 <= end1) // 左区间有剩余
  43.         {
  44.             tmp[i++] = nums[begin1++];
  45.         }
  46.         while (begin2 <= end2) // 右区间有剩余
  47.         {
  48.             tmp[i++] = nums[begin2++];
  49.         }
  50.  
  51.         // 拷贝
  52.         for (int i = 0; i < n; i++)
  53.         {
  54.             nums[i + begin] = tmp[i];
  55.         }
  56.     }
  57. };

2. 交易逆序对的总数（困难）

如果我们将数组划分为左右两个区间，那么逆序对的选择有3种情况，3种情况下逆序对的总和就是整个数组逆序对的总数。

逆序对中两个元素：

  • 全部从左区间中选择
  • 全部从右区间中选择
  • 一个从左区间中选择，一个从右区间中选择

思路恰好对应了归并排序：递归排序两个子区间，合并两个有序子区间。

我们可以结合归并排序，求出逆序对的数量：

  • 求出左区间中逆序对的数量，并对区间排序
  • 求出右区间中逆序对的数量，并对区间排序
  • 求出“一个从左区间中选择，一个从右区间中选择”的逆序对的数量，并合并两个有序子区间

那么，“一个从左区间中选择，一个从右区间中选择”的逆序对的数量，如何求？

方法一：针对右区间的某数，统计左区间中有多少数比它大。

升序排序的情况：

处理剩余元素：

  • 如果左区间有剩余，剩余元素都> 右区间的所有元素，但是它们都已经被统计过了，不会再产生逆序对，直接把剩余元素接到tmp数组后面即可。
  • 如果右区间有剩余，剩余元素都>= 左区间的所有元素，不会产生逆序对，直接把剩余元素接到tmp数组后面即可。

降序排序的情况：

处理剩余元素：

  • 如果左区间有剩余，剩余元素都<= 右区间的所有元素，不会产生逆序对，直接把剩余元素接到tmp数组后面即可。
  • 如果右区间有剩余，剩余元素都< 左区间的所有元素，但是它们都没有被统计过，循环把end1 - begin1 + 1添加到答案并把剩余元素逐个接到tmp数组后面。

显然，方法一用升序排序比降序排序简单，因为不用特殊处理剩余元素。

升序排序版：

  1. class Solution {
  2. public:
  3.     int reversePairs(vector<int>& record) {
  4.         return mergeSort(record, 0, record.size() - 1);
  5.     }
  6.  
  7. private:
  8.     int mergeSort(vector<int>& nums, int begin, int end)
  9.     {
  10.         // 递归出口
  11.         if (begin >= end)
  12.             return 0;
  13.         // 划分左右两个子区间
  14.         int mid = (begin + end) / 2;
  15.         int ans = 0;
  16.         // 分别将左右两个区间的逆序对的数量添加进答案中
  17.         ans += mergeSort(nums, begin, mid);
  18.         ans += mergeSort(nums, mid + 1, end);
  19.         // 将“一个从左区间中选择，一个从右区间中选择”的逆序对的数量添加进答案中
  20.         ans += merge(nums, begin, mid, end);
  21.         return ans;
  22.     }
  23.  
  24.     // 求出“一个从左区间中选择，一个从右区间中选择”的逆序对的数量，并合并两个有序子区间
  25.     int merge(vector<int>& nums, int begin, int mid, int end)
  26.     {
  27.         int n = end - begin + 1;
  28.         vector<int> tmp(n);
  29.         int begin1 = begin, end1 = mid;
  30.         int begin2 = mid + 1, end2 = end;
  31.         int i = 0;
  32.         int ans = 0;
  33.  
  34.         // 升序排序
  35.         int j1 = begin1, j2 = begin2;
  36.         while (j1 <= end1 && j2 <= end2)
  37.         {
  38.             if (nums[j1] <= nums[j2])
  39.             {
  40.                 tmp[i++] = nums[j1++];
  41.             }
  42.             else
  43.             {
  44.                 ans += end1 - j1 + 1;
  45.                 tmp[i++] = nums[j2++];
  46.             }
  47.         }
  48.         while (j1 <= end1) // 左区间有剩余
  49.         {
  50.             tmp[i++] = nums[j1++];
  51.         }
  52.         while (j2 <= end2) // 右区间有剩余
  53.         {
  54.             tmp[i++] = nums[j2++];
  55.         }
  56.  
  57.         // 拷贝
  58.         for (int i = 0; i < n; i++)
  59.         {
  60.             nums[i + begin] = tmp[i];
  61.         }
  62.  
  63.         return ans;
  64.     }
  65. };

降序排序版：

  1. class Solution {
  2. public:
  3.     int reversePairs(vector<int>& record) {
  4.         return mergeSort(record, 0, record.size() - 1);
  5.     }
  6.  
  7. private:
  8.     int mergeSort(vector<int>& nums, int begin, int end)
  9.     {
  10.         // 递归出口
  11.         if (begin >= end)
  12.             return 0;
  13.         // 划分左右两个子区间
  14.         int mid = (begin + end) / 2;
  15.         int ans = 0;
  16.         // 分别将左右两个区间的逆序对的数量添加进答案中
  17.         ans += mergeSort(nums, begin, mid);
  18.         ans += mergeSort(nums, mid + 1, end);
  19.         // 将“一个从左区间中选择，一个从右区间中选择”的逆序对的数量添加进答案中
  20.         ans += merge(nums, begin, mid, end);
  21.         return ans;
  22.     }
  23.  
  24.     // 求出“一个从左区间中选择，一个从右区间中选择”的逆序对的数量，并合并两个有序子区间
  25.     int merge(vector<int>& nums, int begin, int mid, int end)
  26.     {
  27.         int n = end - begin + 1;
  28.         vector<int> tmp(n);
  29.         int begin1 = begin, end1 = mid;
  30.         int begin2 = mid + 1, end2 = end;
  31.         int i = 0;
  32.         int ans = 0;
  33.  
  34.         // 降序排序
  35.         int j1 = begin1, j2 = begin2;
  36.         while (j1 <= end1 && j2 <= end2)
  37.         {
  38.             if (nums[j1] > nums[j2])
  39.             {
  40.                 tmp[i++] = nums[j1++];
  41.             }
  42.             else
  43.             {
  44.                 ans += j1 - begin1;
  45.                 tmp[i++] = nums[j2++];
  46.             }
  47.         }
  48.         while (j1 <= end1) // 左区间有剩余
  49.         {
  50.             tmp[i++] = nums[j1++];
  51.         }
  52.         while (j2 <= end2) // 右区间有剩余
  53.         {
  54.             ans += end1 - begin1 + 1;
  55.             tmp[i++] = nums[j2++];
  56.         }
  57.  
  58.         // 拷贝
  59.         for (int i = 0; i < n; i++)
  60.         {
  61.             nums[i + begin] = tmp[i];
  62.         }
  63.  
  64.         return ans;
  65.     }
  66. };

方法二：针对左区间的某数，统计右区间中有多少数比它小。

升序排序的情况：

处理剩余元素：

  • 如果左区间有剩余，剩余元素都> 右区间的所有元素，但是它们都没有被统计过，循环把end2 - begin2 + 1添加到答案并把剩余元素逐个接到tmp数组后面。
  • 如果右区间有剩余，剩余元素都>= 左区间的所有元素，不会产生逆序对，直接把剩余元素接到tmp数组后面即可。

降序排序的情况：

处理剩余元素：

  • 如果左区间有剩余，剩余元素都<= 右区间的所有元素，不会产生逆序对，直接把剩余元素接到tmp数组后面即可。
  • 如果右区间有剩余，剩余元素都< 左区间的所有元素，但是它们都已经被统计过了，不会再产生逆序对，直接把剩余元素接到tmp数组后面即可。

显然，方法二用降序排序比升序排序简单，因为不用特殊处理剩余元素。

升序排序版：

  1. class Solution {
  2. public:
  3.     int reversePairs(vector<int>& record) {
  4.         return mergeSort(record, 0, record.size() - 1);
  5.     }
  6.  
  7. private:
  8.     int mergeSort(vector<int>& nums, int begin, int end)
  9.     {
  10.         // 递归出口
  11.         if (begin >= end)
  12.             return 0;
  13.         // 划分左右两个子区间
  14.         int mid = (begin + end) / 2;
  15.         int ans = 0;
  16.         // 分别将左右两个区间的逆序对的数量添加进答案中
  17.         ans += mergeSort(nums, begin, mid);
  18.         ans += mergeSort(nums, mid + 1, end);
  19.         // 将“一个从左区间中选择，一个从右区间中选择”的逆序对的数量添加进答案中
  20.         ans += merge(nums, begin, mid, end);
  21.         return ans;
  22.     }
  23.  
  24.     // 求出“一个从左区间中选择，一个从右区间中选择”的逆序对的数量，并合并两个有序子区间
  25.     int merge(vector<int>& nums, int begin, int mid, int end)
  26.     {
  27.         int n = end - begin + 1;
  28.         vector<int> tmp(n);
  29.         int begin1 = begin, end1 = mid;
  30.         int begin2 = mid + 1, end2 = end;
  31.         int i = 0;
  32.         int ans = 0;
  33.  
  34.         // 升序排序
  35.         int j1 = begin1, j2 = begin2;
  36.         while (j1 <= end1 && j2 <= end2)
  37.         {
  38.             if (nums[j2] < nums[j1])
  39.             {
  40.                 tmp[i++] = nums[j2++];
  41.             }
  42.             else
  43.             {
  44.                 ans += j2 - begin2;
  45.                 tmp[i++] = nums[j1++];
  46.             }
  47.         }
  48.         while (j1 <= end1) // 左区间有剩余
  49.         {
  50.             ans += end2 - begin2 + 1;
  51.             tmp[i++] = nums[j1++];
  52.         }
  53.         while (j2 <= end2) // 右区间有剩余
  54.         {
  55.             tmp[i++] = nums[j2++];
  56.         }
  57.  
  58.         // 拷贝
  59.         for (int i = 0; i < n; i++)
  60.         {
  61.             nums[i + begin] = tmp[i];
  62.         }
  63.  
  64.         return ans;
  65.     }
  66. };

降序排序版：

  1. class Solution {
  2. public:
  3.     int reversePairs(vector<int>& record) {
  4.         return mergeSort(record, 0, record.size() - 1);
  5.     }
  6.  
  7. private:
  8.     int mergeSort(vector<int>& nums, int begin, int end)
  9.     {
  10.         // 递归出口
  11.         if (begin >= end)
  12.             return 0;
  13.         // 划分左右两个子区间
  14.         int mid = (begin + end) / 2;
  15.         int ans = 0;
  16.         // 分别将左右两个区间的逆序对的数量添加进答案中
  17.         ans += mergeSort(nums, begin, mid);
  18.         ans += mergeSort(nums, mid + 1, end);
  19.         // 将“一个从左区间中选择，一个从右区间中选择”的逆序对的数量添加进答案中
  20.         ans += merge(nums, begin, mid, end);
  21.         return ans;
  22.     }
  23.  
  24.     // 求出“一个从左区间中选择，一个从右区间中选择”的逆序对的数量，并合并两个有序子区间
  25.     int merge(vector<int>& nums, int begin, int mid, int end)
  26.     {
  27.         int n = end - begin + 1;
  28.         vector<int> tmp(n);
  29.         int begin1 = begin, end1 = mid;
  30.         int begin2 = mid + 1, end2 = end;
  31.         int i = 0;
  32.         int ans = 0;
  33.  
  34.         // 降序排序
  35.         int j1 = begin1, j2 = begin2;
  36.         while (j1 <= end1 && j2 <= end2)
  37.         {
  38.             if (nums[j2] >= nums[j1])
  39.             {
  40.                 tmp[i++] = nums[j2++];
  41.             }
  42.             else
  43.             {
  44.                 ans += end2 - j2 + 1;
  45.                 tmp[i++] = nums[j1++];
  46.             }
  47.         }
  48.         while (j1 <= end1) // 左区间有剩余
  49.         {
  50.             tmp[i++] = nums[j1++];
  51.         }
  52.         while (j2 <= end2) // 右区间有剩余
  53.         {
  54.             tmp[i++] = nums[j2++];
  55.         }
  56.  
  57.         // 拷贝
  58.         for (int i = 0; i < n; i++)
  59.         {
  60.             nums[i + begin] = tmp[i];
  61.         }
  62.  
  63.         return ans;
  64.     }
  65. };

3. 计算右侧小于当前元素的个数（困难）

本题是上一题“逆序对”方法二——“针对左区间的某数，统计右区间中有多少数比它小”的拓展。

根据逆序对的经验，方法二用降序排序比升序排序简单，因为不用特殊处理剩余元素。

需要一个索引数组将数组元素和对应的下标绑定在一起。

  1. class Solution {
  2. public:
  3.     vector<int> countSmaller(vector<int>& nums) {
  4.         int n = nums.size();
  5.         ans.resize(n);
  6.         index.resize(n);
  7.         // 初始化索引数组
  8.         for (int i = 0; i < n; i++)
  9.         {
  10.             index[i]  = i;
  11.         }
  12.         mergeSort(nums, 0, n - 1);
  13.         return ans;
  14.     }
  15.  
  16. private:
  17.     void mergeSort(vector<int>& nums, int begin, int end)
  18.     {
  19.         // 递归出口
  20.         if (begin >= end)
  21.             return;
  22.         // 划分左右两个子区间
  23.         int mid = (begin + end) / 2;
  24.         // 递归处理左右两个区间
  25.         mergeSort(nums, begin, mid);
  26.         mergeSort(nums, mid + 1, end);
  27.         // 处理“针对左区间的某数，统计右区间中有多少数比它小”
  28.         merge(nums, begin, mid, end);
  29.         return;
  30.     }
  31.  
  32.     // 针对左区间的某数，统计右区间中有多少数比它小，并合并两个有序子区间
  33.     void merge(vector<int>& nums, int begin, int mid, int end)
  34.     {
  35.         int n = end - begin + 1;
  36.         vector<int> tmpNums(n); // 排序用的辅助数组
  37.         vector<int> tmpIndex(n); // 处理下标用的辅助数组
  38.         int begin1 = begin, end1 = mid;
  39.         int begin2 = mid + 1, end2 = end;
  40.         int i = 0;
  41.  
  42.         // 降序排序
  43.         int j1 = begin1, j2 = begin2;
  44.         while (j1 <= end1 && j2 <= end2)
  45.         {
  46.             if (nums[j2] >= nums[j1])
  47.             {
  48.                 tmpNums[i] = nums[j2];
  49.                 tmpIndex[i++] = index[j2++];
  50.             }
  51.             else
  52.             {
  53.                 ans[index[j1]] += end2 - j2 + 1;
  54.                 tmpNums[i] = nums[j1];
  55.                 tmpIndex[i++] = index[j1++];
  56.             }
  57.         }
  58.         while (j1 <= end1) // 左区间有剩余
  59.         {
  60.             tmpNums[i] = nums[j1];
  61.             tmpIndex[i++] = index[j1++];
  62.         }
  63.         while (j2 <= end2) // 右区间有剩余
  64.         {
  65.             tmpNums[i] = nums[j2];
  66.             tmpIndex[i++] = index[j2++];
  67.         }
  68.  
  69.  
  70.         // 拷贝
  71.         for (int i = 0; i < n; i++)
  72.         {
  73.             nums[i + begin] = tmpNums[i];
  74.             index[i + begin] = tmpIndex[i];
  75.         }
  76.     }
  77.  
  78.     vector<int> ans;
  79.     vector<int> index; // 索引数组，index[j]保存当前nums[j]的原始下标
  80. };

4. 翻转对（困难）

和逆序对类似，所以也可以用归并排序的思想解决问题。

如果我们将数组划分为左右两个区间，那么翻转对的选择有3种情况，3种情况下翻转对的总和就是整个数组翻转对的总数。

翻转对中两个元素：

  • 全部从左区间中选择
  • 全部从右区间中选择
  • 一个从左区间中选择，一个从右区间中选择

和逆序对不同的是，逆序对是在合并有序区间过程中，计算出翻转对的数量，对于翻转对，我们要先计算出翻转对的数量，再合并。

“一个从左区间中选择，一个从右区间中选择”的翻转对的数量，如何求？

方法一：针对右区间的某数，统计左区间中有多少数比它的2倍大。

根据逆序对的经验，方法一用升序排序比降序排序简单，因为不用特殊处理剩余元素。

  1. class Solution {
  2. public:
  3.     int reversePairs(vector<int>& nums) {
  4.         return mergeSort(nums, 0, nums.size() - 1);
  5.     }
  6.  
  7. private:
  8.     int mergeSort(vector<int>& nums, int begin, int end)
  9.     {
  10.         // 递归出口
  11.         if (begin >= end)
  12.             return 0;
  13.         // 划分左右两个子区间
  14.         int mid = (begin + end) / 2;
  15.         int ans = 0;
  16.         // 分别将左右两个区间的翻转对的数量添加进答案中
  17.         ans += mergeSort(nums, begin, mid);
  18.         ans += mergeSort(nums, mid + 1, end);
  19.         // 将“一个从左区间中选择，一个从右区间中选择”的翻转对的数量添加进答案中
  20.         ans += merge(nums, begin, mid, end);
  21.         return ans;
  22.     }
  23.  
  24.     // 求出“一个从左区间中选择，一个从右区间中选择”的翻转对的数量，并合并两个有序子区间
  25.     int merge(vector<int>& nums, int begin, int mid, int end)
  26.     {
  27.         int begin1 = begin, end1 = mid;
  28.         int begin2 = mid + 1, end2 = end;
  29.         int ans = 0;
  30.  
  31.         // 升序排序的情况下翻转对的数量
  32.         int j1 = begin1, j2 = begin2;
  33.         while (j1 <= end1 && j2 <= end2)
  34.         {
  35.             while (j1 <= end1 && nums[j1] / 2.0 <= nums[j2]) // 防止2 * nums[j2]溢出
  36.             {
  37.                 j1++;
  38.             }
  39.             if (j1 > end1)
  40.                 break;
  41.             ans += end1 - j1 + 1;
  42.             j2++;
  43.         }
  44.  
  45.         // 合并升序排序的两个区间
  46.         int n = end - begin + 1;
  47.         vector<int> tmp(n);
  48.         int i = 0;
  49.         j1 = begin1;
  50.         j2 = begin2;
  51.         while (j1 <= end1 && j2 <= end2)
  52.         {
  53.             if (nums[j1] < nums[j2])
  54.             {
  55.                 tmp[i++] = nums[j1++];
  56.             }
  57.             else
  58.             {
  59.                 tmp[i++] = nums[j2++];
  60.             }
  61.         }
  62.         while (j1 <= end1) // 左区间有剩余
  63.         {
  64.             tmp[i++] = nums[j1++];
  65.         }
  66.         while (j2 <= end2) // 右区间有剩余
  67.         {
  68.             tmp[i++] = nums[j2++];
  69.         }
  70.  
  71.         // 拷贝
  72.         for (int i = 0; i < n; i++)
  73.         {
  74.             nums[i + begin] = tmp[i];
  75.         }
  76.         return ans;
  77.     }
  78. };

方法二：针对左区间的某数，统计右区间中有多少数的2倍比它小。

根据逆序对的经验，方法二用降序排序比升序排序简单，因为不用特殊处理剩余元素。

  1. class Solution {
  2. public:
  3.     int reversePairs(vector<int>& nums) {
  4.         return mergeSort(nums, 0, nums.size() - 1);
  5.     }
  6.  
  7. private:
  8.     int mergeSort(vector<int>& nums, int begin, int end)
  9.     {
  10.         // 递归出口
  11.         if (begin >= end)
  12.             return 0;
  13.         // 划分左右两个子区间
  14.         int mid = (begin + end) / 2;
  15.         int ans = 0;
  16.         // 分别将左右两个区间的翻转对的数量添加进答案中
  17.         ans += mergeSort(nums, begin, mid);
  18.         ans += mergeSort(nums, mid + 1, end);
  19.         // 将“一个从左区间中选择，一个从右区间中选择”的翻转对的数量添加进答案中
  20.         ans += merge(nums, begin, mid, end);
  21.         return ans;
  22.     }
  23.  
  24.     // 求出“一个从左区间中选择，一个从右区间中选择”的翻转对的数量，并合并两个有序子区间
  25.     int merge(vector<int>& nums, int begin, int mid, int end)
  26.     {
  27.         int begin1 = begin, end1 = mid;
  28.         int begin2 = mid + 1, end2 = end;
  29.         int ans = 0;
  30.  
  31.         // 降序排序的情况下翻转对的数量
  32.         int j1 = begin1, j2 = begin2;
  33.         while (j1 <= end1 && j2 <= end2)
  34.         {
  35.             while (j2 <= end2 && nums[j2] >= nums[j1] / 2.0) // 防止2 * nums[j2]溢出
  36.             {
  37.                 j2++;
  38.             }
  39.             if (j2 > end2)
  40.                 break;
  41.             ans += end2 - j2 + 1;
  42.             j1++;
  43.         }
  44.  
  45.         // 合并降序排序的两个区间
  46.         int n = end - begin + 1;
  47.         vector<int> tmp(n);
  48.         int i = 0;
  49.         j1 = begin1;
  50.         j2 = begin2;
  51.         while (j1 <= end1 && j2 <= end2)
  52.         {
  53.             if (nums[j1] > nums[j2])
  54.             {
  55.                 tmp[i++] = nums[j1++];
  56.             }
  57.             else
  58.             {
  59.                 tmp[i++] = nums[j2++];
  60.             }
  61.         }
  62.         while (j1 <= end1) // 左区间有剩余
  63.         {
  64.             tmp[i++] = nums[j1++];
  65.         }
  66.         while (j2 <= end2) // 右区间有剩余
  67.         {
  68.             tmp[i++] = nums[j2++];
  69.         }
  70.  
  71.         // 拷贝
  72.         for (int i = 0; i < n; i++)
  73.         {
  74.             nums[i + begin] = tmp[i];
  75.         }
  76.         return ans;
  77.     }
  78. };

5. 排序链表（中等）

分治的思想，类似归并排序：

  1. 划分两个子链表

  2. 分别对两个子链表进行排序，形成两个有序链表

  3. 合并两个有序链表

重复的子问题——函数头设计

ListNode* sortList(ListNode* head)

子问题在做什么——函数体设计

  1. 划分两个子链表，找中间节点：ListNode* mid = midNode(head);
  2. 递归排序右子链表：ListNode* l1 = sortList(mid->next);
  3. 断开两个子链表：mid->next = nullptr;
  4. 递归排序左子链表：ListNode* l2 = sortList(head);
  5. 合并两个有序链表：return mergeTowList(l1, l2);

递归出口

当链表只有一个节点时，不合并。另外，当题目给出空链表时，不合并。

  1. class Solution {
  2. public:
  3.     ListNode* sortList(ListNode* head) {
  4.         if (head == nullptr || head->next == nullptr)
  5.             return head;
  6.  
  7.         ListNode* mid = midNode(head); // 中间节点
  8.         ListNode* l1 = sortList(mid->next); // 排序右子链表
  9.         mid->next = nullptr; // 断开两个子链表
  10.         ListNode* l2 = sortList(head); // 排序左子链表
  11.         return mergeTwoLists(l1, l2); // 合并两个有序链表
  12.     }
  13.  
  14. private:
  15.     // 快慢指针找链表的中间节点，如果节点个数为偶数，取靠左的
  16.     ListNode* midNode(ListNode* head)
  17.     {
  18.         ListNode* fast = head;
  19.         ListNode* slow = head;
  20.         // 慢指针每次走1步，快指针每次走2步
  21.         // 如果节点个数为奇数，当快指针指向最后一个节点时，慢指针指向中间节点
  22.         // 如果节点个数为奇数，当快指针指向倒数第二个节点时，慢指针指向靠左的中间节点
  23.         while (fast->next && fast->next->next)
  24.         {
  25.             fast = fast->next->next;
  26.             slow = slow->next;
  27.         }
  28.         return slow;
  29.     }
  30.     // 合并两个有序链表
  31.     ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
  32.     {
  33.         ListNode* preHead = new ListNode; // 哨兵节点
  34.         ListNode* tail = preHead;
  35.  
  36.         // 取小的尾插
  37.         while (list1 && list2)
  38.         {
  39.             if (list1->val < list2->val)
  40.             {
  41.                 tail->next = list1;
  42.                 tail = tail->next;
  43.                 list1 = list1->next;
  44.             }
  45.             else
  46.             {
  47.                 tail->next = list2;
  48.                 tail = tail->next;
  49.                 list2 = list2->next;
  50.             }
  51.         }
  52.  
  53.         if (list1)
  54.         {
  55.             tail->next = list1;
  56.         }
  57.         if (list2)
  58.         {
  59.             tail->next = list2;
  60.         }
  61.  
  62.         return preHead->next;
  63.     }
  64. };

6. 合并 K 个升序链表（困难）

6.1 递归解法（归并）

分治的思想，类似归并排序：

  1. 划分两个子区间

  2. 分别对两个子区间的链表进行合并，形成两个有序链表

  3. 合并两个有序链表

重复的子问题——函数头设计

ListNode* merge(vector<ListNode*>& lists, int begin, int end)

子问题在做什么——函数体设计

  1. 划分两个子区间：int mid = (begin + end) / 2;
  2. 递归合并两个子区间：
    ListNode* l1 = merge(lists, begin, mid);
    ListNode* l2 = merge(lists, mid + 1, end);
  3. 合并两个有序链表：return mergeTowList(l1, l2);

递归出口

当区间只有一个链表时，不合并。另外，当题目给出空链表时，不合并。

  1. class Solution {
  2. public:
  3.     ListNode* mergeKLists(vector<ListNode*>& lists) {
  4.         return merge(lists, 0, lists.size() - 1);
  5.     }
  6.  
  7. private:
  8.     ListNode* merge(vector<ListNode*>& lists, int begin, int end)
  9.     {
  10.         if (begin > end)
  11.             return nullptr;
  12.         if (begin == end)
  13.             return lists[begin];
  14.  
  15.         int mid = (begin + end) / 2;
  16.         ListNode* l1 = merge(lists, begin, mid);
  17.         ListNode* l2 = merge(lists, mid + 1, end);
  18.         return mergeTwoLists(l1, l2);
  19.     }
  20.     ListNode* mergeTwoLists(ListNode* list1, ListNode* list2)
  21.     {
  22.         ListNode* preHead = new ListNode; // 哨兵节点
  23.         ListNode* tail = preHead;
  24.  
  25.         // 取小的尾插
  26.         while (list1 && list2)
  27.         {
  28.             if (list1->val < list2->val)
  29.             {
  30.                 tail->next = list1;
  31.                 tail = tail->next;
  32.                 list1 = list1->next;
  33.             }
  34.             else
  35.             {
  36.                 tail->next = list2;
  37.                 tail = tail->next;
  38.                 list2 = list2->next;
  39.             }
  40.         }
  41.  
  42.         if (list1)
  43.         {
  44.             tail->next = list1;
  45.         }
  46.         if (list2)
  47.         {
  48.             tail->next = list2;
  49.         }
  50.  
  51.         return preHead->next;
  52.     }
  53. };

6.2 迭代解法（堆）

和“合并两个有序链表”类似，就是取小的尾插。怎么判断K个链表未合并的头节点中最小的那个？利用堆这个数据结构即可。把K个链表未合并的头节点放进一个小根堆，堆顶就是最小的那个。

  1. class Solution {
  2. public:
  3.     ListNode* mergeKLists(vector<ListNode*>& lists) {
  4.         // 创建小根堆
  5.         priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
  6.         // 将所有头节点放进小根堆
  7.         for (auto& l : lists)
  8.         {
  9.             if (l)
  10.             {
  11.                 heap.push(l);
  12.             }
  13.         }
  14.         // 合并链表
  15.         ListNode* preHead = new ListNode; // 哨兵节点
  16.         ListNode* tail = preHead;
  17.         while (!heap.empty())
  18.         {
  19.             // 取堆顶节点尾插
  20.             tail->next = heap.top();
  21.             heap.pop();
  22.             tail = tail->next;
  23.             // 将刚才合并的节点的下一个节点补充进堆
  24.             if (tail->next)
  25.             {
  26.                 heap.push(tail->next);
  27.             }
  28.         }
  29.         return preHead->next;
  30.     }
  31.  
  32. private:
  33.     struct cmp
  34.     {
  35.         bool operator()(ListNode* n1, ListNode* n2)
  36.         {
  37.             return n1->val > n2->val;
  38.         }
  39.     };
  40. };
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/编程挑战者/article/detail/61196
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号