【Leetcode刷题篇】剑指offer51 数组中的逆序对
发布日期:2021-06-29 15:33:46
浏览次数:2
分类:技术文章
本文共 2351 字,大约阅读时间需要 7 分钟。
在解决该问题之前,先来看一下归并排序。
// 归并排序 public static void mergeSort(int[] arr) { if(arr==null || arr.length<2) { return; } sortProcess(arr,0,arr.length-1); } public static void sortProcess(int[] arr,int L,int R) { if(L==R) { return; } int mid = L + ((R-L) >> 1); sortProcess(arr, L, mid); sortProcess(arr, mid+1, R); merge(arr,L,mid,R); } public static void merge(int[] arr,int L,int mid,int R) { int[] temp = new int[R-L+1]; int i = 0; int p1 = L; int p2 = mid + 1; while(p1<=mid&&p2<=R) { temp[i++] = arr[p1]
此题 与小数和问题类似
小和问题 在一个数组中,每一个数左边比当前数小的数累加起来,叫做这个数组的小和。求一个数组 的小和。 例子: [1,3,4,2,5] 1左边比1小的数,没有; 3左边比3小的数,1; 4左边比4小的数,1、3; 2左边比2小的数,1; 5左边比5小的数,1、3、4、2; 所以小和为1+1+3+1+1+3+4+2=16
public static int smallSum(int[] arr) { if(arr==null||arr.length<2) { return 0; } return mergeSort_2(arr,0,arr.length-1); } public static int mergeSort_2(int[] arr,int L,int R) { // 终止条件 if(L==R) { return 0; } int mid = L + ((R-L)>>1); return mergeSort_2(arr,L,mid) + mergeSort_2(arr,mid+1,R)+merge_2(arr,L,mid,R); } public static int merge_2(int[] arr,int L,int mid,int R) { int[] temp = new int[R-L+1]; int i = 0; int p1 = L; int p2 = mid+1; int res = 0; while(p1<=mid&&p2<=R) { res += arr[p1]
而本题在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。
package com.lcz.leetcode;/** * 数组中的逆序对 * @author LvChaoZhang * */public class Leetcode_offer51 { class Solution{ public int reversePairs(int[] nums) { if(nums==null||nums.length<2) { return 0; } return mergeSort(nums,0,nums.length-1); } public int mergeSort(int[] nums,int L,int R) { // 终止条件 if(L==R) { return 0; } int mid = L + ((R-L)>>1); int leftPairs = mergeSort(nums, L, mid); int rightPairs = mergeSort(nums, mid+1, R); if(nums[mid]<=nums[mid+1]) { return leftPairs+rightPairs; } int crossPairs = merge(nums,L,mid,R); return leftPairs+rightPairs+crossPairs; } public int merge(int[] arr,int L,int mid,int R) { int[] temp = new int[R-L+1]; int res = 0; int i = 0; int p1 = L; int p2 = mid+1; while(p1<=mid&&p2<=R) { res += arr[p1]>arr[p2]?(mid-p1+1):0; temp[i++] = arr[p1]<=arr[p2]?arr[p1++]:arr[p2++]; } while(p1<=mid) { temp[i++] = arr[p1++]; } while(p2<=R) { temp[i++] = arr[p2++]; } for(i=0;i
转载地址:https://codingchaozhang.blog.csdn.net/article/details/109690916 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
表示我来过!
[***.240.166.169]2024年04月27日 16时19分13秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
做DSP最应该懂得157个问题
2019-04-30
Jenkins 连接github
2019-04-30
android中是Aspect 进行埋点笔记
2019-04-30
android中 java编写的test 类 mock kotlin 对象问题笔记
2019-04-30
牛客网 找到搜索二叉树中两个错误的节点
2019-04-30
牛客网. 未排序正数数组中累加和为给定值的最长子数组的长度
2019-04-30
牛客题霸. 未排序数组中累加和为给定值的最长子数组长度
2019-04-30
牛客网. 未排序数组中累加和为给定值的最长子数组系列问题补2
2019-04-30
笔记:基本Markdown使用总结
2019-04-30
m4s转为mp4实例:使用ffmpeg和批处理将m4s转为mp4
2019-04-30
批处理实例:图片批量重命名
2019-04-30
## 对第一个java程序进行总结
2019-04-30
java基本语法之标识符、数据类型
2019-04-30
基本数据类型之间的运算规则:
2019-04-30