逆序对-----归并排序
本周遇到了一道蛮有意思的题目，分享给大家欣赏一下！这道题使用归并排序。原来在力扣上刷题时，也遇到过一次归并的思路，不过当时一知半解，就跳过去了，心想着以后遇到了再深究一下，结果很快就遇到了----天注定啊！那我们这次一起来看看这个排序思想吧！
我们首先来介绍一下归并排序！
归并排序
归并排序主要是对一个无序的数组进行不断的对半切分为更小的数组，直到最小的数组元素个数为0或1，然后再将所有被切分的元素进行重新排序，每一次都会得到一个新的有序小数组，最后将这些小的有序数组合并起来，得到一个最终整体有序的数组。我们来看一下整个过程的示意图：
归并排序示意图
数组中的逆序对
《剑指offer》--------- 数组中的逆序对 题目描述
题目描述
简单的说就是给定一个数组，数组中每个元素的前面都有k个大于当前元素的数，将每个元素的k相加，得到整个数组的逆序对。
1、解决思路
解决这道题目可以使用经典的排序算法------归并排序。
对于本题，我们可以将其进行一个转化：利用归并算法，将数组A进行排序，在分割的时候，直到数组的元素个数为0或1，才开始进行排序，所以在排序的过程中，逐一去对比左右数组的元素大小，如果left[i]>right[j]，则在当前合并过程中，对于right[j]的逆序对为left[i]~left[end-1]。
由此我们便解决了当前的问题。
2、代码实现
public class Solution {
int res = 0;
//使用归并思路
public int InversePairs(int [] array) {
MergeCut(array,0,array.length-1);
return res;
}
//分割
private void MergeCut(int[] array, int start, int end){
if(start >= end){
return;
}
int mid = (end-start)/2 + start;
MergeCut(array,start,mid);//left
MergeCut(array,mid+1,end);//right
MergeSort(array,start,mid,end);
}
//排序
private void MergeSort(int[] array, int start, int mid, int end){
int[] temp = new int[end - start + 1];
int left = start, right = mid+1, index = 0;
while(left <= mid && right <= end){
if(array[left] > array[right]){
res = (res + mid - left + 1)%1000000007;
temp[index++] = array[right++];
}else{
temp[index++] = array[left++];
}
}
while(left <= mid){
temp[index++] = array[left++];
}
while(right <= end){
temp[index++] = array[right++];
}
//将temp赋值给原数组array
for(int i = 0 ; i < temp.length ; i++){
array[start++] = temp[i];
}
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-04-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录