目录
例1
例2
例3
例4
例1
912. 排序数组
参考代码
class Solution {
public:
vector<int> tmpnums;
vector<int> sortArray(vector<int>& nums) {
tmpnums.resize(nums.size());
mergeSort(nums, 0, nums.size() - 1);
return nums;
}
void mergeSort(vector<int>& nums, int left, int right)
{
if(left >= right) return;
int mid = (left + right) >> 1;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
int cur1 = left, cur2 = mid + 1, i = left;
while(cur1 <= mid && cur2 <= right)
tmpnums[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
while(cur1 <= mid)
tmpnums[i++] = nums[cur1++];
while(cur2 <= right)
tmpnums[i++] = nums[cur2++];
for(int i = left; i <= right; i++)
nums[i] = tmpnums[i];
}
};例2
LCR 170. 交易逆序对的总数
这里的nums就是record
①升序：nums[cur1]和nums[cur2]比较，小的放到tmp数组里，也随之++，如果用cur1来对应区间[mid + 1, cur2] 的话会重复，因为这时候nums[cur1] > nums[cur2]，却是cur2++，这会导致cur1，重复配对区间
②降序：降序是把大的往tmp里面放，nums[cur1]大的时候正好又++，不会重复
参考代码
class Solution {
public:
vector<int> tmp;
int reversePairs(vector<int>& record) {
tmp.resize(record.size());
return mergeSort(record, 0, record.size() - 1);
}
int mergeSort(vector<int>& record, int left, int right)
{
int ret = 0;
if(left >= right) return ret;
int mid = (left + right) >> 1;
ret += mergeSort(record, left, mid);
ret += mergeSort(record, mid + 1, right);
int cur1 = left, cur2 = mid + 1, i = left;
while(cur1 <= mid && cur2 <= right)
{
// if(record[cur1] <= record[cur2])
// {
// tmp[i++] = record[cur1++];
// }
// else
// {
// ret += mid - cur1 + 1;
// tmp[i++] = record[cur2++];
// }
if(record[cur1] <= record[cur2])
{
tmp[i++] = record[cur2++];
}
else
{
ret += right - cur2 + 1;
tmp[i++] = record[cur1++];
}
}
while(cur1 <= mid) tmp[i++] = record[cur1++];
while(cur2 <= right) tmp[i++] = record[cur2++];
for(int i = left; i <= right; i++)
{
record[i] = tmp[i];
}
return ret;
}
};例3
315. 计算右侧小于当前元素的个数
解释：①给nums绑定一个index数组，，通过index[cur1]得到这个数对应的最初始的下标，也就是这一步：ret[index[cur1]] += right - cur2 + 1;
②使用降序方便，因为题目是求，某个值的右边比他值小的个数，cur1正好是左边的区间，就不会导致ret数组的第一元素为0，且使用cur1，可以使ret数组最后一个值为0，其二升序的逻辑就是不对的，降序原理是cur2去左边找比它大的，但是这里要去右边找，所以只能用降序做
错误：①写回时for写错while，②tmpIndex[i++] = index[cur2++]；对应成nums[cur2++],导致堆溢出，③注意最后一个for是<= 因为区间是[left, right]
参考代码
class Solution {
public:
vector<int> tmpNums, index, tmpIndex, ret;
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
tmpNums.resize(n);
index.resize(n);
tmpIndex.resize(n);
ret.resize(n);
for(int i = 0; i < nums.size(); i++)
index[i] = i;
mergeSort(nums, 0, n - 1);
return ret;
}
void mergeSort(vector<int>& nums, int left, int right)
{
if(left >= right) return;
int mid = (left + right) >> 1;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
int cur1 = left, cur2 = mid + 1, i = left;
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;
tmpNums[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
}
while(cur1 <= mid)
{
tmpNums[i] = nums[cur1];
tmpIndex[i++] = index[cur1++];
}
while(cur2 <= right)
{
tmpNums[i] = nums[cur2];
tmpIndex[i++] = index[cur2++];
}
for(int i = left; i <= right; i++)
{
nums[i] = tmpNums[i];
index[i] = tmpIndex[i];
}
}
};例4
493. 翻转对
解析：在合并前计算个数，升序降序都可以
下面两段，效果一样
while(cur1 <= mid && cur2 <= right)
{
while(cur2 <= right && nums[cur1] / 2.0 <= nums[cur2]) cur2++;
ret += right - cur2 + 1;
cur1++;
}while(cur1 <= mid && cur2 <= right)
{
if(nums[cur1] / 2.0 > nums[cur2])
ret += right - cur2 + 1, cur1++;
else
cur2++;
}降序参考代码
class Solution {
public:
vector<int> tmp;
int reversePairs(vector<int>& nums) {
tmp.resize(nums.size());
return mergeSort(nums, 0, nums.size() - 1);
}
int mergeSort(vector<int>& nums, int left, int right)
{
if(left >= right) return 0;
int mid = (left + right) >> 1;
int ret = 0;
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
int cur1 = left, cur2 = mid + 1, i = left;
while(cur1 <= mid && cur2 <= right)
{
while(cur2 <= right && nums[cur1] / 2.0 <= nums[cur2]) cur2++;
ret += right - cur2 + 1;
cur1++;
}
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 i = left; i <= right; i++)
{
nums[i] = tmp[i];
}
return ret;
}
};升序参考代码
class Solution {
public:
vector<int> tmp;
int reversePairs(vector<int>& nums) {
tmp.resize(nums.size());
return mergeSort(nums, 0, nums.size() - 1);
}
int mergeSort(vector<int>& nums, int left, int right)
{
if(left >= right) return 0;
int mid = (left + right) >> 1;
int ret = 0;
ret += mergeSort(nums, left, mid);
ret += mergeSort(nums, mid + 1, right);
int cur1 = left, cur2 = mid + 1, i = left;
while(cur1 <= mid && cur2 <= right)
{
while(cur1 <= mid && nums[cur1] / 2.0 <= nums[cur2]) cur1++;
ret += mid - cur1 + 1;
cur2++;
}
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 i = left; i <= right; i++)
{
nums[i] = tmp[i];
}
return ret;
}
};
