剑指offer——数组中的逆序对
程序员文章站
2022-05-10 15:33:36
...
剑指offer——数组中的逆序对
题目描述
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
输入描述:
题目保证输入的数组中没有的相同的数字
数据范围:
对于%50的数据,size<=10^4
对于%75的数据,size<=10^5
对于%100的数据,size<=2*10^5
示例1
输入:1,2,3,4,5,6,7,0
输出:7
第一解答思路:暴力求解
利用两个for循环,遍历求解,时间复杂度为O(n*n)。
package com.offer;
class Solution {
public static int InversePairs(int [] array) {
int len=array.length;
if(len==0 || array==null){
return 0;
}
int p=0;
for(int i=0;i<len;i++){
for(int j=i+1;j<len;j++){
if(array[i]>array[j]){
p++;
}
}
}
return p%1000000007;
}
}
public class InversePairsTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] a={1,2,3,4,5,6,7,0};
System.out.println(Solution.InversePairs(a));
}
}
第二解答思路:利用归并排序,显著提高查找效率
public class Solution {
int count=0;
public int InversePairs(int [] array) {
if(array.length==0 || array==null){
return 0;
}
mergeSort(array,0,array.length-1);
return count;
}
//归并排序(从上往下)
public void mergeSort(int[] a,int low,int high){
//一定要写递归出口,不然会报错:Exception in thread "main" java.lang.*Error
if(low>=high){
return;
}
int mid=(high+low)>>1;
mergeSort(a,low,mid);
mergeSort(a,mid+1,high);
merge(a,low,mid,high);
}
//将一个数组中的两个相邻有序区间合并成一个
public void merge(int[] a,int low,int mid,int high){
int[] temp=new int[high-low+1];
int i=low,j=mid+1,k=0;//i代表左半部分,j代表右半部分,k为临时数组的下标
while(i<=mid && j<=high){
if(a[i]<=a[j]){
temp[k++]=a[i++];
}else{
temp[k++]=a[j++];
count += mid-i+1;
//核心算法。因为前半部分为有序序列,则如果a[i]>a[j],则a[i]到a[mid]之间的元素都大于a[j]
//因为j++,所以要一次求完,即mid-i+1
count %=1000000007;
}
}
while(i<=mid){
temp[k++]=a[i++];
}
while(j<=high){
temp[k++]=a[j++];
}
for(int m=0;m<temp.length;m++){
a[low+m]=temp[m];
}
}
}
参考学习资料:JAVA算法——排序之归并排序
上一篇: 数组的逆序对个数
推荐阅读
-
剑指offer31:整数中1出现的次数(从1到n整数中1出现的次数)
-
剑指offer28:找出数组中超过一半的数字。
-
剑指offer27:按字典序打印出该字符串中字符的所有排列
-
C#版剑指Offer-001二维数组中的查找
-
剑指offer11:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。(进制转换,补码反码)
-
剑指offer JZ31 整数中1出现的次数 Python 解
-
剑指offer JZ54 字符流中第一个不重复的字符 Python 多解
-
剑指Offer积累-JZ1-二维数组中的查找
-
剑指offer之队列中的最大值(C++/Java双重实现)
-
剑指offer之在排序数组中查找数字 I(C++/Java双重实现)