归并排序算法题
小和问题
题目要求我们计算数组的小和 完整的题目和示例如下
该题目出自于牛客网编程题 – 数组的小和
做这道题目最笨的方法就是多次遍历整个数组 每次找当前位置的小和 很显然这样子做的时间复杂度是N的平方 使用这种解法在面试的过程中是没有分数的！
所以我们必须要想出一个更加优秀的解法出来 实际上我们可以利用归并排序每两个数只比较一次的特点来解决
首先我们回答下下面这个问题
找出数组中所有的小和 是不是等价于将数组从左到右的比较一遍找出小于数字出现的次数啊
如果说一个数字在比较的时候小于另外一个数字 我们就叫它小于数字
比如说数组中只有两个元素3和4 在比较的时候我们即可以说有一个数字3也可以说3出现了一次 最后得到的结果是等价的
而我们使用归并排序的过程就是这个从左到右比较的过程
代码运行如下
#include <iostream> using namespace std; #include <vector> long long Merge(vector<int>& nums , int left , int mid , int right) { vector<int> temp(right-left+1, 0); int i = left; int j = mid + 1; int k = 0; long long SUM = 0; while(i <= mid && j <= right) { if (nums[i] <= nums[j]) { // small sum SUM += (right - j + 1) * nums[i]; temp[k] = nums[i]; i++; } else { temp[k] = nums[j]; j++; } k++; } while(i <= mid) { temp[k++] = nums[i++]; } while(j <= right) { temp[k++] = nums[j++]; } for (i = left ; i <= right ; i++) { nums[i] = temp[i - left]; } return SUM; } long long SmallNums(vector<int>& nums , int left , int right) { if (left >= right) { return 0; } int mid = left + (right - left) / 2; return SmallNums(nums, left, mid) + SmallNums(nums, mid + 1, right) + Merge(nums, left, mid, right); } int main() { long n = 0; cin >> n; vector<int> nums(n , 0); for (int i = 0; i < n ; i++) { cin >> nums[i]; } long long sum = SmallNums(nums, 0, n-1); cout << sum; return 0; }
我们可以发现 实际上这段代码对比归并排序只多出了一行代码
- 一行代码
SUM += (right - j + 1) * nums[i];
这就是计算小和的步骤了
运行结果如下
翻转对问题
让你计算一个数组中的翻转对 题目和示例出现在lc493题
值得我们注意的是 该翻转对的下标必须要是左下标小于右下标 也就是说该翻转对必须要按照从左到右的顺序 并且只比较一遍 这里我们就应该想到使用我们的归并排序了
但是题目中的要求并不是单纯的大于小于 而是一个大于两倍的关系
这其实就是这道题目相比较于其他考查归并排序题目的一个难点 解决方案是这样子的
我们首先找出符合题目要求的数据 最后再进行归并排序
使用这个思路去解决问题就好了
也就是说归并之前我们先用一段代码来找到答案 代码表示如下
int MergeAndFind(vector<int>& nums , int left , int mid , int right) { int ans = 0; int windowr = mid + 1; for (int i = left ; i <= mid ; i++) { while(windowr <= right && nums[i] > (long)(nums[windowr] << 1)) { windowr++; } ans += windowr - mid - 1; } vector<int> help(right - left + 1 , 0); int i = left; int j = mid + 1; int k = 0; while(i <= mid && j <= right) { if (nums[i] <= nums[j]) { help[k] = nums[i]; i++; } else { help[k] = nums[j]; j++; } k++; } while(i <= mid) { help[k++] = nums[i++]; } while (j <= right) { help[k++] = nums[j++]; } for (i = left ; i <= right ; i++) { nums[i] = help[i - left]; } return ans; }
剩下的代码就是单纯的归并排序了 没有什么好讲解的 完整代码如下
class Solution { public: int MergeAndFind(vector<int>& nums , int left , int mid , int right) { int ans = 0; int windowr = mid + 1; for (int i = left ; i <= mid ; i++) { while(windowr <= right && (long long)nums[i] >((long long)nums[windowr] * 2)) { windowr++; } ans += windowr - mid - 1;ii } vector<int> help(right - left + 1 , 0); int i = left; int j = mid + 1; int k = 0; while(i <= mid && j <= right) { if (nums[i] <= nums[j]) { help[k] = nums[i]; i++; } else { help[k] = nums[j]; j++; } k++; } while(i <= mid) { help[k++] = nums[i++]; } while (j <= right) { help[k++] = nums[j++]; } for (i = left ; i <= right ; i++) { nums[i] = help[i - left]; } return ans; } int _reversPairs(vector<int>& nums , int left , int right) { if (left >= right) { return 0; } int mid = left + (right - left) / 2; return _reversPairs(nums , left , mid) + _reversPairs(nums , mid + 1 , right) + MergeAndFind(nums , left , mid , right); } int reversePairs(vector<int>& nums) { return _reversPairs(nums , 0 , nums.size() -1); } };
这道题目注意的有两点
- 我们乘2必须要使用 “ * ” 运算符 不能使用位运算 否则负数就有可能出问题
- 在进行乘法的时候要进行类型转换 不然可能会有数据溢出的问题
以上就是归并排序的写法以及归并排序思想可以解决的一些面试题
