java简单实现数组中的逆序对
作者:zz0129 时间:2022-06-26 02:23:17
题目描述:
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
解题思路:
一开始一头雾水,后面想到了使用归并排序的思想,其实有多少个逆序对,就是归并排序的时候,后面的数要超越前面多少个,嗯,好像不是很好说,要不然直接看代码吧。还要注意,题目当中说要输出取模的结果,这说明数据可能非常大,所以如果只是单纯的在最后取模的话可能还是无法避免数据太大的影响,所以我们在每次更新count的时候就对其进行取模运算。
刚好又练习了一遍归并排序,记录一下
public class Solution {
int count;
public int InversePairs(int [] array) {
count = 0;
if(array != null){
divPairs(array, 0, array.length-1);
}
return count%1000000007;
}
public void divPairs(int[] array, int start, int end){
if(start >= end)
return;
int mid = (start + end)>>1;
divPairs(array, start, mid);
divPairs(array, mid+1, end);
mergePairs(array, start, mid, end);
}
public void mergePairs(int[] array, int start, int mid, int end){
int i = start, j = mid+1, k = 0;
int[] temp = new int[end-start+1];
while(i <= mid && j <= end){
if(array[i] <= array[j]){
temp[k++] = array[i++];
}else{
temp[k++] = array[j++];
count += mid - i + 1;
count %= 1000000007;
}
}
while(i <= mid){
temp[k++] = array[i++];
}
while(j <= end){
temp[k++] = array[j++];
}
for(int x = 0; x < temp.length; x++){
array[start+x] = temp[x];
}
}
}
来源:https://blog.csdn.net/zz0129/article/details/81321778
标签:java,数组,逆序对
0
投稿
猜你喜欢
详解java 中Spring jsonp 跨域请求的实例
2023-11-19 02:48:18
C++右值引用与move和forward函数的使用详解
2023-07-05 19:27:33
redisson 实现分布式锁的源码解析
2022-06-05 05:38:47
java小程序之控制台字符动画的实现
2022-10-30 08:21:27
简单了解4种分布式session解决方案
2023-08-09 11:45:49
java中TESTful架构原理分析
2022-03-02 21:12:10
spring boot多数据源动态切换代码实例
2022-03-11 00:37:09
JAVA中的日期时间类用法总结
2023-08-29 08:00:24
Java内存模型JMM详解
2023-11-28 13:08:50
unity实现贴图矩阵运算(旋转平移缩放)
2022-07-27 13:53:41
详解Android中点击事件的几种实现方式
2022-07-03 09:05:09
使用Java的Lucene搜索工具对检索结果进行分组和分页
2022-07-27 05:21:17
Java 实战项目之疫情人员流动管理系统详解
2022-08-04 19:30:57
Android实现歌词渐变色和进度的效果
2023-09-24 02:33:17
IDEA搭建SpringBoot离线工程的方法
2023-04-11 05:50:42
Java使用组件编写窗口实现网上文件下载
2023-09-14 06:08:36
网易Java程序员两轮面试 请问你能答对几个?
2023-11-29 10:32:08
关于Java中BeanMap进行对象与Map的相互转换问题
2023-09-18 07:25:36
Java集合TreeSet用法详解
2023-11-10 22:53:34
Android实现自动提取短信验证码功能
2022-11-19 23:58:49