程序地带

数组中的逆序对 - 剑指Offer第51题


在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。


示例 :


输入: [7,5,6,4] 输出: 5


解题思路:


参考LeetCode解题思路: https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/shu-zu-zhong-de-ni-xu-dui-by-leetcode-solution/


package com.alibaba.study.offer;
/**
* @Auther: wjj
* @Date: 2020/12/14 21:14
* @Description:
*/
public class Offer51 {
public static void main(String[] args) {
System.out.printf("结果:" + reversePairs(new int[] {7,5,6,4}));
}
public static int reversePairs(int[] nums) {
int len = nums.length;
if(len < 2){
return 0;
}
int[] temp = new int[len];
return merge(nums, 0, len-1, temp);
}
private static int merge(int[] nums, int left, int right, int[] temp){
if(left == right){
return 0;
}
// 当left和right非常大时,可能会溢出
int mid = left + (right - left)/ 2;
int leftCount = merge(nums, left, mid, temp);
int rightCount = merge(nums, mid + 1, right, temp);
// 如果左数组最大值比右数组最小值小,那么无逆序对
if(nums[mid] <= nums[mid + 1]){
return leftCount + rightCount;
}
// 计算两个有序数组的逆序对
int crossCount = caculateCorssCount(nums, left, mid, right, temp);
return leftCount + crossCount + rightCount;
}
private static int caculateCorssCount(int[] nums, int left, int mid, int right, int[] temp) {
for(int i=left; i<=right; i++){
temp[i] = nums[i];
}
int i = left;
int j = mid + 1;
int count = 0;
for(int k = left; k<= right; k++){
if(i == mid + 1){
nums[k] = temp[j];
j++;
} else if(j == right + 1){
nums[k] = temp[i];
i++;
} else if(temp[i] <= temp[j]){
nums[k] = temp[i];
i++;
} else {
// 只有右数组元素入数组时,才需要计算逆序对,理解一下,
// 右数组元素入原数组,表示这个元素值比左数组剩余的值都要小,
// 构成逆序对。
nums[k] = temp[j];
j++;
count += (mid-i+1);
}
}
return count;
}
}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Faker_Wang/article/details/111246084

随机推荐

和csm_干翻CSM,LCF的威敏男装本科有多牛

和csm_干翻CSM,LCF的威敏男装本科有多牛

标题非标题党,威斯敏斯特大学的服装设计一直就是在国内被严重低估。学Fashion的同学都知道现任BURBERRY创意总监ChristopherBailey,都知道祖师爷级别...

weixin_39585070 阅读(451)

2021-01-09

2021-01-09

LinuxUbuntu小窗口调成全屏现在打算好好学习IT知识,创建一个博客账户记录一下学习过程中遇到的困难以及后来的解决方法。打开终端对话框,输入xrand,并且回车&#x...

xiaobeiyaokaixin 阅读(842)

使用promise报错_Promise实现原理解析

使用promise报错_Promise实现原理解析

前言大家平时基本上都听过或者用过Promise,大部分基本都是拿来主义(当然也包括我),而对于原理知之甚少,这样不利于日后问题的排...

weixin_39533280 阅读(370)