首页 > 试题广场 >

逆序对距离之和

[编程题]逆序对距离之和
  • 热度指数:2593 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小易给定一个的排列,希望你能求出这个序列中所有逆序对的距离和。
下标的距离为,逆序对是指序列中一对下标满足 .

输入描述:
第一行数字表示排列长度 
接下来一行个数字表示这个排列



输出描述:
一行一个数字表示答案
示例1

输入

5  
1 3 4 2 5

输出

3

说明

逆序对:
(3, 2)距离为2
(4, 2)距离为1
总和为3
import java.util.*;
 
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][2];
        for(int i=0;i<n;i++){
            arr[i][0] = sc.nextInt();
            arr[i][1] = i;
        }
        long res = getAns(arr,n);
        System.out.println(res);
    }
     
    public static long getAns(int[][] arr,int n){
        int[][] tmp = new int[n][2];
        return reverse(arr,0,n-1,tmp);
    }
    
    public static long reverse(int[][] arr,int left,int right,int[][] tmp){
        if(left>=right)
            return 0;
        int mid = (left+right)>>>1;
        long leftDistance = reverse(arr,left,mid,tmp);
        long rightDistance = reverse(arr,mid+1,right,tmp);
        if(arr[mid][0]<=arr[mid+1][0])
            return leftDistance+rightDistance;
        long crossDistance = reverseCross(arr,left,mid,right,tmp);
        return crossDistance+leftDistance+rightDistance;
    }
    
    public static long reverseCross(int[][] arr,int left,int mid,int right,int[][] tmp){
        for(int i=left;i<=right;i++){
            tmp[i][0] = arr[i][0];
            tmp[i][1] = arr[i][1];
        }
        int i = left,j = mid+1;
        long count = 0;
        for(int k=left;k<=right;k++){
            if(i==mid+1){
                arr[k][0] = tmp[j][0];
                arr[k][1] = tmp[j][1];
                j++;
            }else if(j==right+1){
                arr[k][0] = tmp[i][0];
                arr[k][1] = tmp[i][1];
                i++;
            }else if(tmp[i][0]<=tmp[j][0]){
                arr[k][0] = tmp[i][0];
                arr[k][1] = tmp[i][1];
                i++;
            }else if(tmp[i][0]>tmp[j][0]){
                arr[k][0] = tmp[j][0];
                arr[k][1] = tmp[j][1];
                for(int l=i;l<=mid;l++){
                    count+=tmp[j][1]-tmp[l][1];
                }
                j++;
            }
        }
        return count;
    }
}
Java代码,用的归并排序方法,用二维数组分别记录值和索引,注意count要用long类型。
发表于 2020-08-06 12:13:09 回复(0)
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int sum = 0;
        scanner.nextLine();
        String str = scanner.nextLine();
        String[] arrStr = str.split("\\s");
        int[] arrInt = new int[arrStr.length];
        for (int i = 0; i < arrStr.length; i++) {
            arrInt[i] = Integer.parseInt(arrStr[i]);
        }
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (arrInt[i] > arrInt[j]) {
                    sum += (j - i);
                }
            }
        }
        System.out.println(sum);

    }
}

编辑于 2020-01-05 14:07:10 回复(1)