求两个数组的逆序数——Kendall tau距离

野性酷女 2022-09-30 07:28 179阅读 0赞

一组排列（或是排名）就是一组N个整数的数组，其中0到N-1的每个数都只出现一次。两个排列之间的Kendall tau距离就是在两组数列中顺序不同的数对的数目。例如a = \{ 0, 3, 1, 6, 2, 5, 4 \} ，b = \{ 1, 0, 3, 6, 4, 2, 5 \}，Kendall tau就是4，因为就是求两个排列之间的逆序\{ 0，1 \}，\{ 3，1 \}，\{ 2，4 \}，\{ 5，4 \}，一共为4对，故Kendall tau距离为4。

import java.util.*;
    
    
    /**
     * Created by Megustas on 2017/3/20.
     */
    
    
    public class Exercise{
        
        public static int distance(int[] a,int[] b){
            if(a.length!=b.length){
               throw new IllegalArgumentException("Array dimensions disagree");
            }
            int[] aIndex = new int[a.length];
            int[] bIndex = new int[b.length];
            //用数组aIndex存储数组a的索引值,可以看做（i，a[i]）,（i,b[i]）
            for (int i=0;i<a.length;i++){
                aIndex[a[i]] = i;
            }
            //bIndex数组引用A数组的索引，即bIndex数组存储b数组元素在a数组中的对应位置
            for (int i=0;i<b.length;i++){
                bIndex[i]=aIndex[b[i]];
            }
            return sortcount(bIndex);
        }
    
        public static int sortcount(int[] a){
            int length = a.length;
            int counter = 0;
            //插入排序的交换次数就是倒置数
            for (int i=1;i<length;i++){
                for (int j=i;j>0&&a[j]<a[j-1];j--){
                    int temp = a[j];
                    a[j] = a[j-1];
                    a[j-1] = temp;
                    counter++;
                }
            }
            return counter;
        }
    
        public static void main(String[] args) {
            int[] a = {
       0,3,1,6,2,5,4};
            int[] b = {
       1,0,3,6,4,2,5};
            for (int i = 0;i < a.length;i++){
                System.out.println(a[i] + " " +b[i]);
            }
            System.out.println("Kendall tau :" + Exercise.distance(a,b));
        }
    
    }

提示：**插入排序需要的交换操作和数组中倒置的数量相同，因为每次交换都改变了两个顺序颠倒的元素位置，相当于减少了一对倒置，当倒置数量为0时，排序就完成了。**