AlgoPressAppearance
51-数组中的逆序对
题目描述
https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
- 0 <= 数组长度 <= 50000
思路
暴力法，就是选中一个数，往后遍历比他小的计数到对应的位置中，最后统计所有的总数，暴力法应该会超时
解决的重点是将两层循环改造成一层循环
代码
csharp
public class Solution {
public int ReversePairs(int[] nums) {
int count = 0;
for(int i=0; i<nums.Length -1; i++){
for(int j = i+1; j<nums.Length; j++){
if(nums[i] > nums[j]){
count++ ;
}
}
}
return count;
}
}
本题动态规划和单调栈都不适用
思路2：归并排序并技术【官方】
归并排序，假设两个数组都是有序的，将他们合并到一个数组中去。 nums1, nums2 当 nums2[i] 小于 nums1[i] 的时候，优先合并 nums2[i] 到数组中去，此时nums1还剩余多少个数，就可以构成多少个逆序对(因为两边都是有序的) 对整个 nums 数组，可以使用分治法，即不停的分拆到只剩一个数字，那么必然是有序的，然后归并并且计算逆序对返回上来。
代码
csharp
public class Solution {
public int ReversePairs(int[] nums) {
if(nums.Length < 2){
return 0; //小于2不构成逆序对
}
//构造 copy 数组去处理
int[] copy = new int[nums.Length];
for(int i=0; i<nums.Length; i++){
copy[i] = nums[i];
}
//构造 temp 数组用于交换
int[] temp = new int[nums.Length];
return ReversePairs(copy,0,nums.Length-1,temp);
}
private int ReversePairs(int[] nums, int left, int right, int[] temp){
if(left == right){
return 0;
}
int mid = left + (right - left)/2;
int leftPairs = ReversePairs(nums, left, mid, temp);
int rightPairs = ReversePairs(nums, mid+1, right, temp);
//计算合并
int count = mergeAndCount(nums, left, mid, right, temp);
return leftPairs + rightPairs + count;
}
private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp){
int i = left;
int j = mid + 1;
int k = left;
int count = 0;
while(i <= mid || j <= right){
//处理已经越界
if(i>mid){
//只处理右边
temp[k] = nums[j];
j++;
}
else if(j>right){
temp[k] = nums[i];
i++;
}
else if(nums[i] <= nums[j]){
temp[k] = nums[i];
i++;
}
else{
temp[k] = nums[j];
j++;
count += mid - i + 1;
}
k++;
}
//复制回去到 nums
for(i=left;i<=right;i++){
nums[i] = temp[i];
}
return count;
}
}
代码复习
注意 MergeSort 的写法
csharp
public class Solution {
int count = 0;
private void MergeSort(int[] arr, int[] tmp, int start, int end){
if(start == end){
return;
}
int mid = start + (end-start)/2;
MergeSort(arr,tmp,start,mid);
MergeSort(arr,tmp,mid+1,end);
int t=start;
int i=start;
int j=mid+1;
while(i<=mid || j<=end){
if(i>mid){
tmp[t] = arr[j];
j++;
}
else if(j>end){
tmp[t] = arr[i];
i++;
}
else if(arr[i] <= arr[j]){
tmp[t] = arr[i];
i++;
}
else{
tmp[t] = arr[j];
count += mid - i + 1;
//Console.WriteLine("count = {0} for {1}",count, arr[j]);
j++;
}
t++;
}
//将temp复制到arr
for(int k=start;k<=end;k++){
arr[k]=tmp[k];
}
}
public int ReversePairs(int[] nums) {
if(nums.Length <2){
return 0;
}
//复制一个数组
int[] arr = new int[nums.Length];
int[] tmp = new int[nums.Length];
for(int i=0; i<nums.Length; i++){
arr[i] = nums[i];
}
MergeSort(arr,tmp,0,nums.Length-1);
return count;
}
}
复习:20220603
csharp
public class Solution {
int count = 0;
public int ReversePairs(int[] nums) {
//归并排序
int n = nums.Length;
int[] temp = new int[n];
MergeSort(nums,0,n-1,temp);
return count;
}
private void MergeSort(int[] nums, int start, int end, int[] temp){
if(start >= end){
return;
}
int mid = start + (end - start) / 2;
MergeSort(nums,start,mid,temp);
MergeSort(nums,mid+1,end,temp);
// start .. mid, mid+1 .. end
int index = start;
int index1 = start;
int index2 = mid+1;
while(index1 <= mid || index2 <= end){
if(index2 > end){
temp[index] = nums[index1];
index1++;
}
else if(index1 > mid){
temp[index] = nums[index2];
index2++;
}
else if(nums[index1] <= nums[index2]){
temp[index] = nums[index1];
index1++;
}
else{
temp[index] = nums[index2];
count+= mid - index1 + 1;
index2++;
}
index++;
}
//复制内容回去
for(int i=start; i<=end; i++){
nums[i] = temp[i];
}
}
}