当前位置：首页 > news >正文

数组中的逆序对

news 来源：原创 2024/5/19 7:30:54

题目描述
有一组数，对于其中任意两个数组，若前面一个大于后面一个数字，则这两个数字组成一个逆序对。请设计一个高效的算法，计算给定数组中的逆序对个数。

给定一个int数组A和它的大小n，请返回A中的逆序对个数。保证n小于等于5000。

测试样例：
[1,2,3,4,5,6,7,0],8
返回：7

对于每一个index为i的元素，需要统计index为0~i-1的元素中值大于它的个数，通过构建二叉树维护0~i-1的数据

import java.util.*;

public class AntiOrder {
    
    Node root;
    
    public int count(int[] A, int n) {
        // write code here
        if(n==0)
            return 0;
        root = new Node(A[0]);
        int res = 0;
        for(int i=1; i<n; i++){
            root.insert(A[i]);
            res += root.getRank(A[i]);
        }
        return res;
    }
}

class Node{
    int val;
    Node left;
    Node right;
    
    Node(int v){
        val = v;
    }
    int leftSize = 0;
    
    public void insert(int v){
        if(v>val){
            if(left!=null)
                left.insert(v);
            else{
                left = new Node(v);
            }
            leftSize += 1;
        }else{
            if(right!=null)
                right.insert(v);
            else
                right = new Node(v);
        }
    }
    
    public int getRank(int v){
        if(v==val)
            return leftSize;
        else if(v>val){
            return left.getRank(v);
        }
        else{
            return leftSize + 1 + right.getRank(v);
        }
    }
}

二分法

统计每一个小段内部的逆序对，在合并时统计段之间的逆序对数

import java.util.*;

public class AntiOrder {
    public int count(int[] A, int n) {
        // write code here
        return c(A, 0, n-1);
    }
    
    public int c(int[] A, int left, int right){
        if(left>=right)
            return 0;
        int mid = left + (right-left)/2;
        int count1 = c(A, left, mid);
        int count2 = c(A, mid+1, right);
        return count1 + count2 + merge(A, left, mid, right);
    }
    
    public int merge(int [] A, int left, int mid, int right){
        int [] temp = new int[right-left+1+1];
        int k = 0;
        int i=left, j=mid+1;
        int result = 0;
        while(i<=mid&&j<=right){
            if(A[i]<A[j])
                temp[k++] = A[i++];
            else{
                result += mid-i+1;
                temp[k++] = A[j++];
            }
        }
        while(i<=mid)
            temp[k++] = A[i++];
        while(j<=right)
            temp[k++] = A[j++];
        for(int p=left; p<=right; p++)
            A[p] = temp[p-left];
        return result;
    }
}