首页 > 试题广场 >

数组中的逆序对

[编程题]数组中的逆序对
  • 热度指数:8036 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解

给定一个int数组A和它的大小n,对于这组数能组成的任意两个数组,若前面一个大于后面一个数字,则这两个数字组成一个逆序对。请设计一种高效的算法返回A中存在的逆序对个数。要求n不大于5000。

测试样例:
[1,2,3,4,5,6,7,0],8
返回:7
import java.util.*;
//这个题和上一个求数组的秩是类似的,逆序对=当前数组长度 - 秩,
//在秩的基础上,把左右子树对调一下就可以了,在秩的基础上修改两个不等号就ok了
public class AntiOrder {
    	Node root = null;

	public int count(int[] A, int n) {
		int res = 0;
		for (int i = 0; i < n; i++) {
			res  += helper(A[i]);
		}
		return res;
	}

	public int helper(int a) {
		if (root == null) {
			root = new Node(a);
			return 0;
		} else {
			root.insert(a);
			return root.getRank(a);
		}
	}
}

class Node {
	int leftSize = 0;
	Node left, right;
	int val;

	public Node(int v) {
		val = v;
	}

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

	public int getRank(int v) {
		if (v == val)
			return leftSize;
		if (v > val)
			return left.getRank(v);
		if (v < val)
			return leftSize + 1 + right.getRank(v);
		return 0;
	}
}

发表于 2015-09-10 15:32:38 回复(0)
/*
[1,2,3,4,5,6,7,0],8
7
类似11.8,也可以用multiset(底层为红黑树)做,
以0为例,end-cur即为0的逆序对数目
*/
class AntiOrder {
public:
	int count(vector<int> A, int n) {
		// write code here
		int ret = 0;
		multiset<int> mset;
		multiset<int>::iterator cur, end;

		for (int i = 0; i < n; i++)
		{
			mset.insert(A[i]);
			cur = mset.upper_bound(A[i]);
			end = mset.end();
			while (cur != end)
			{
				ret++;
				cur++;
			}
		}

		return ret;
	}
};

发表于 2017-02-21 10:55:15 回复(0)











int merge(int[] A, int start, int mid, int end) {

int[] aux = new int[end - start + 1];

int i = start;

int j = mid + 1;

int k = 0;

int reverse = 0;

while (i <= mid && j <= end) {

if (A[i] <= A[j]) {

aux[k++] = A[i++];

} else {

reverse += mid - i + 1;

aux[k++] = A[j++];

}

}


while (i <= mid) {

aux[k++] = A[i++];

}

while (j <= end) {

aux[k++] = A[j++];

}


for (int m = 0; m < aux.length; ++m) {

A[start + m] = aux[m];

}


return reverse;

}


public int count(int[] A, int start, int end) {

if (end <= start) {

return 0;

}

int mid = (start + end) >> 1;

int count1 = count(A, start, mid);

int count2 = count(A, mid + 1, end);

return count1 + count2 + merge(A, start, mid, end);

}


public int count(int[] A, int n) {

// write code here

return count(A, 0, n - 1);

}


发表于 2016-04-27 20:50:17 回复(0)
import java.util.*;

public class AntiOrder {
    public int count(int[] A, int n) {
        int sum=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++)
                if(A[i]>A[j])
                    sum++;
        }
        return sum;
    }
}
发表于 2018-09-16 22:19:35 回复(0)
class AntiOrder {
public:
    //归并排序,前面一块数据中没出现一个值比后面值的数,则前面之后的数都比后面的该数大
    void merge_sort(vector& A,int start,int end,vector& tmp,int& count)
    {
        if(start == end)
            return;
        int mid = (start+end)/2;
        merge_sort(A,start,mid,tmp,count);
        merge_sort(A,mid+1,end,tmp,count);
        int i=start,j=mid+1;
        int ind = start;
        while(i<=mid && j<=end)
        {
            if(A[i] > A[j])
            {
                count += mid-i+1;
                tmp[ind++] = A[j++];
            }else
            {
                tmp[ind++] = A[i++];
            }
        }
        while(i <= mid)
        {
            tmp[ind++] = A[i++];
        }
        while(j <= end)
        {
            tmp[ind++] = A[j++];
        }
        for(int k=start;k<=end;++k)
        {
            A[k] = tmp[k];
        }
    }
    int count(vector A, int n) {
        // write code here
        vector tmp(n,0);
        int num = 0;
        merge_sort(A,0,n-1,tmp,num);
        return num;
    }
};
发表于 2020-07-21 23:25:17 回复(0)
class AntiOrder {
public:
    int count(vector<int> A, int n) {
        multiset<int> s;
        int cnt = 0;
        for(int i=0;i<n;i++){
            s.insert(A[i]);
            multiset<int>::iterator p = s.upper_bound(A[i]);
            while(p!=s.end()){
                p++;
                cnt++;             }         }         return cnt;
    }
};

发表于 2019-03-09 01:51:01 回复(0)
import java.util.*;
//其实也就是求一个数左边有少个比它大的,排序后p2之前的数就是p2的所有逆序对 (R-p2+1)
public class AntiOrder {
   public int count(int[] A,int n) {
    if(A == null || n == 0) return 0;
    return mergSort(A,0,A.length-1);
     }
 
   public int mergSort(int[] arr,int L,int R){
         if(L == R) return 0;
         int mid = L+ ((R-L) >> 1);
         return mergSort(arr,L,mid)+mergSort(arr,mid+1,R)+merg(arr,L,mid,R);
        }
 
     public int merg(int[] arr,int L,int mid,int R){
      int[] help = new int[R-L+1];
      int i = 0;
      int count = 0;
      int p1 = L;
      int p2 = mid+1;
      
      while(p1 <= mid && p2 <= R){
       if(arr[p1] > arr[p2]){
           count += (mid-L)+1;    
        help[i++] = arr[p2++];
       }else{
        help[i++] = arr[p1++];
                }
            }
      
      while(p1 <= mid){
       help[i++] = arr[p1++];
            }
      
      while(p2 <= R){
       help[i++] = arr[p2++];
            }
      
      for (int j = 0; j < help.length; j++) {
    arr[L + j] = help[j];
            }
      
      return count;
        }

}


编辑于 2021-03-18 18:24:33 回复(0)
//遍历数组,如果前面的值比后面的值大,就是一个逆序对。时间复杂度O(n*n).
//O(nlogn)的算法是采用归并排序。
class AntiOrder {
public:
    int count(vector<int> A, int n) {
        int count = 0;
        for(int i = 0;i < n-1;++i)
        {
            for(int j = i;j < n;++j)
            {
                if(A[i] > A[j])
                    count++;
            }
        }
        return count;
    }
};


编辑于 2018-08-28 11:46:17 回复(0)
import java.util.*;
/*
错误的思路:先排序,再对比排序后的数字和排序前的数字位置,相同数字在不同位置之间的位置差的数目就是逆序对的数目
如何找相同数字的不同位置~用二分法可以降复杂度,时间复杂度O(nlogn)
很想知道我这个思路哪里错了啊!!!求大神解释
正确的思路:归并排序
*/
/*
public class AntiOrder {
    public int count(int[] A, int n) {
        int b[] =new int[n];
        int j=0;
        int sum=0;
        for(int m:A){
            b[j]=m;
            j++;
        }
        Arrays.sort(b);
        for(j=0;j<n;j++){
            int start=0;
            int end =n-1;
            int mid=0;
            while(start<=end){
                mid =(start+end)/2;
                if(A[j]==b[mid]) break;
                else if(A[j]>b[mid]) start=mid+1;
                else end =mid-1;
            }
            if(mid-j>0) sum=sum+mid-j;
        }
        return sum;
    }
}
*/
public class AntiOrder {
    public int count(int[] A, int n) {
        if(A==null||A.length==0) return 0;
        int []copy=new int[n];
        for(int i=0;i<n;i++){
            copy[i]=A[i];
        }
        return mergesort(A,copy,0,n-1);
        
    }
    public int mergesort(int[] A,int[] copy,int start,int end){
        if(start==end){ 
            copy[start] =A[start];
        	return 0;
        }
        int mid=(start+end)/2;
        int left =mergesort(copy,A,start,mid);
//这里要注意了,copy和A的数组互换了,实际上我们比较的都是copy中的数组值,而不是A的数组值
//因为copy中数组是一直保持分段数组内部顺序的(即每次逆序对计算完,都会把计算完的逆序对顺序调整)
//用copy数组比较才不会出现重复计算逆序对的情况,这里如果不互换顺序会多计算无数次逆序对
        int right =mergesort(copy,A,mid+1,end);
        int i=mid,j=end,count=0,index=end;
        while(i>=start&&j>mid){
            if(A[i]>A[j]){
                count +=j-mid;
                copy[index--]=A[i--];
            }else{
                copy[index--]=A[j--];
            }
        }
        while(i>=start){
            copy[index--]=A[i--];
        }
        while(j>mid){
			copy[index--]=A[j--];
        }
        return count+left+right;
    }
}
运行时间:205ms
占用内存:13612k

发表于 2017-07-05 17:17:56 回复(0)
归并排序
class AntiOrder {
public:
    int mergeSort(vector<int>& A, vector<int>& temp, int left, int right)
    {
        if (left >= right) return 0;
        int reverseCount = 0;
        int mid = (left + right) >> 1;
        reverseCount += mergeSort(A, temp, left, mid);
        reverseCount += mergeSort(A, temp, mid + 1, right);
        int pos, i, j;
        for (pos = left,i = left, j = mid + 1; j <= right; ++j)
        {
            while (i <= mid && A[i] < A[j])
            {
                temp[pos] = A[i];
                ++pos;
                ++i;
            }
            if (i <= mid) reverseCount += mid - i + 1;
            temp[pos] = A[j];
            ++pos;
        }
        while (i <= mid) temp[pos++] = A[i++];
        memcpy(A.data() + left, temp.data() + left, (right - left + 1) * sizeof(int));
        return reverseCount;
    }

    int count(vector<int> A, int n)
    {
        vector<int> temp(n, 0);
        return mergeSort(A, temp, 0, n - 1);
    }
};

发表于 2017-06-30 14:46:22 回复(0)
class AntiOrder:
    def count(self, A, n):
        self.rNums = 0
        self.mergeSort(A)
        return self.rNums

    def mergeSort(self, A):
        if len(A) <= 1:
            return A
        m = len(A) / 2
        a = self.mergeSort(A[:m])
        b = self.mergeSort(A[m:])
        return self.merge(a, b)

    def merge(self, A, B):
        c, i, j = [], 0, 0
        while i < len(A) and j < len(B):
            if A[i] <= B[j]:
                c.append(A[i])
                i += 1
            else:
                c.append(B[j])
                j += 1
                self.rNums += len(A) - i #此为逆序对数
        c += A[i:]
        c += B[j:]
        return c


发表于 2017-03-05 13:53:15 回复(0)
class AntiOrder {
public:
    int count(vector<int> data, int n) {
        // write code here
        if(data.size()<=1) return 0;
        int* copy=new int[data.size()];
        //初始化数组
        for(unsigned int i=0;i<data.size();i++)
            copy[i]=0;
        int count=InversePairCore(data,copy,0,data.size()-1);
        delete[] copy;
        return count;
    }
    
    int InversePairCore(vector<int>& data,int*& copy,int start,int end)
    {
        if(start==end)
        {
            copy[start]=data[start];
            return 0;
        }
        //将数组拆分成两部分
        int length=(end-start)/2;
        //分别计算左边部分和右边部分
        int left=InversePairCore(data,copy,start,start+length)%1000000007;
        int right=InversePairCore(data,copy,start+length+1,end)%1000000007;
        //进行逆序计算
        int i=start+length;
        int j=end;
        int index=end;
        int count=0;
        while(i>=start && j>=start+length+1)
        {
            if(data[i]>data[j])
            {
                copy[index--]=data[i--];
                //统计长度
                count+=j-start-length;
                if(count>=1000000007)//数值过大求余
                    count%=1000000007;
            }
            else
            {
                copy[index--]=data[j--];
            }
        }
        for(;i>=start;--i)
        {
            copy[index--]=data[i];
        }
        for(;j>=start+length+1;--j)
        {
            copy[index--]=data[j];
        }
        //排序
        for(int i=start; i<=end; i++) {
            data[i] = copy[i];
        }
        //返回最终的结果
        return (count+left+right)%1000000007;
    }
};

发表于 2016-08-14 17:32:58 回复(0)
Ron头像 Ron
/*
	 * 数组的逆序对就是当前数组长度-秩,与上题一样,维护一组二叉查找树,每次添加新值后得到该数组对应的秩,用当前数组长度-秩
	 * 对所有值的添加过程都进行逆序对计算,并加和即可
	 */
	public class RankNode{
		public int left_size = 0;
		public RankNode left, right;
		public int data = 0;
		public RankNode(int d) {
			// TODO Auto-generated constructor stub
			data = d;
		}
		public void insert(int d) {
			// TODO Auto-generated method stub
			if(d <= data){
				if(left != null){
					left.insert(d);
				}else{
					left = new RankNode(d);
				}
				left_size++;
			}else{
				if(right != null){
					right.insert(d);
				}else{
					right = new RankNode(d);
				}
			}
		}
		public int getRank(int d) {
			// TODO Auto-generated method stub
			if(d == data){
				return left_size;
			}else if(d < data){
				if(left == null){
					return -1;
				}else{
					return left.getRank(d);
				}
			}else{
				int right_rank = right == null ? -1 : right.getRank(d);
				if(right_rank == -1) return -1;
				return left_size + 1 + right.getRank(d);
			}
		}
	}
    public int count(int[] A, int n) {
        // write code here
    	if(A == null || A.length != n || n <= 0){
    		return 0;
    	}
    	RankNode root = new RankNode(A[0]);
    	int[] ranks = new int[n];
    	int res = 0;
    	for(int i = 1; i < n; i++){
    		root.insert(A[i]);
    		ranks[i] = root.getRank(A[i]);
    		res += i - ranks[i];
    	}
    	return res;
    }
发表于 2016-06-11 23:32:44 回复(0)
Solution: 提供两种解决方案:
 Method 1: brute force O(n^2)
 Method 2: merge sort O(nlogn)

 publicintcount(int[] A, intn) {
        // write code here
        if(A==null|| n==0) return0;
        //Method 2: merge sort
        returnhelper(A,0,n-1);
        /*
        //Method 1: brute force O(n^2)
        int count=0;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(A[i]>A[j]){
                    count++;
                }
            }
        }      
          
        return count;
        */
    }
      
    privateinthelper(int[] A, intstart, intend){
        if(start>=end) return0;
         
        intmid=start + (end-start)/2;
        intleft=helper(A,start, mid);
        intright=helper(A,mid+1,end);
        intcount=mergeCount(A,start,mid,end);
        returnleft+count+right;
    }
      
    privateintmergeCount(int[] A, intstart, intmid, intend){
        intresult=0;
        int[] t=newint[end+1];
        for(inti=start;i<=end;i++){
            t[i]=A[i];
        }
         
        inti=mid,j=end;      
        intk=end;
        while(i>=start && j>=mid+1){
            if(A[i]>=A[j]){
                t[k--]=A[i--];
                result+= j-mid;
            }else{
                t[k--]=A[j--];
            }
        }
          
        while(i>=start){
            t[k--]=A[i--];
        }
          
        while(j>mid){
            t[k--]=A[j--];
        }
          
        for(intm=start;m<=end;m++){
            A[m]=t[m];
        }
          
        returnresult;
    }
发表于 2016-01-02 15:46:13 回复(0)
大概思路是归并排序的思想,先分为2个左右部分,左部分的逆序对(只在左部分取2个数),右部分的逆序对(只在右部分取2个数),满足在左部分取一个数,右部分取一个数的逆序对,以上全部加起来就是总的逆序对。计算左右部分的逆序对的时候,利用递归。
class Solution {
public:
    int InversePairs(vector<int> data) {
        return merge(data, 0, data.size() - 1);
    }
    int merge_count(vector<int> &data, int start, int mid, int end)//计算满足左部分一个数,右部分一个数条件的逆序对,此时左右部分已排好序
{
	vector<int> temp(data);
	int count = 0;
	int i = start;
	int j = mid + 1;
	int k = start;
	while (i <= mid&&j <= end)
	{
		if (data[i] <=data[j])
			temp[k++] = data[i++];
		else
		{
			temp[k++] = data[j++];
			count = count + mid- i+1;
		}
	}
	while (i <= mid)temp[k++] = data[i++];
	while (j <= end)temp[k++] = data[j++];
	for (int m = start; m <= end; m++)
		data[m] = temp[m];
	return count;
}
int merge(vector<int> &data, int start, int end)//左右部分分别递归,
{
	if (start >= end)
		return 0;
	int mid = (start + end) / 2;
	int left=merge(data, start, mid);
	int right=merge(data, mid + 1, end);
	int count = merge_count(data, start, mid, end);
	return left + right + count;
}
};

发表于 2015-11-04 10:04:32 回复(0)
L0L头像 L0L
//常规思想,找出每个元素的逆序对,复杂度是O(N*N)
//利用归并排序的思想,先划分再合并,复杂度可以降到O(NlogN)
class AntiOrder {
public:
		void merge(vector<int> &v,int a1,int a2,int b1,int b2,int &pairs){
			vector<int> tmp;
			int i=a1;
			int j=b1;
			while(i<=a2&&j<=b2){
				if(v[i]<=v[j]){
					tmp.push_back(v[i++]);
					pairs=pairs+j-b1;
				}
				else{
					tmp.push_back(v[j++]);
				}
			}
			while(i<=a2){
				tmp.push_back(v[i++]);
				pairs=pairs+b2-b1+1;
			}
			while(j<=b2) tmp.push_back(v[j++]);
			for(i=0,j=a1;j<=b2;j++)
				v[j]=tmp[i++];
		}
		void fun(vector<int> &v,int p1,int p2,int &pairs){
			if(p1==p2)
				return;
			fun(v,p1,(p1+p2)/2,pairs);
			fun(v,(p1+p2)/2+1,p2,pairs);
			merge(v,p1,(p1+p2)/2,(p1+p2)/2+1,p2,pairs);
		}
    int count(vector<int> A, int n) {
        int pairs=0;
		fun(A,0,n-1,pairs) ;
		return pairs;
    }
};

编辑于 2015-10-19 21:07:34 回复(0)
/*
冒泡排序时做了多少次交换就有多少个逆序
*/
class AntiOrder {
public:
    int count(vector<int> A, int n) {
        // write code here
        int count = 0;
        int i,j;
        if(n < 2) return n;
        for(i=0;i<n;i++){
            for(j=0;j<n-i-1;j++){
                if(A[j]>A[j+1]){
                    swap(A[j],A[j+1]);
                    count++;
                }
            }
        }
        return count;
    }
};

发表于 2015-09-06 19:07:43 回复(2)
利用归并排序,在对有序子数组进行merge的同时,累加逆序对,时间复杂度O(nlogn)
import java.util.*; public class AntiOrder { public int count(int[] A, int n) { // write code here if (A == null || n == 0) { return 0; } return mergeSortRecursion(A, 0, n - 1); } /** * 递归实现归并排序 * * @param arr * @param l * @param r * @return 返回数组中的逆序对 */ public static int mergeSortRecursion(int[] arr, int l, int r) { if (l == r) { // 当待排序数组长度为1时,递归开始回溯,进行merge操作 return 0; } int mid = (l + r) / 2; return mergeSortRecursion(arr, l, mid) + mergeSortRecursion(arr, mid + 1, r) + merge(arr, l, mid, r); }     /** * 合并两个已排好序的数组s[left...mid]和s[mid+1...right] * * @param arr * @param left * @param mid * @param right * @return 返回合并过程中累加逆序对 */ public static int merge(int[] arr, int left, int mid, int right) { int[] temp = new int[right - left + 1]; // 辅助存储空间 O(n) int index = 0; int i = left; int j = mid + 1; int inverseNum = 0; // 新增,用来累加数组逆序对 while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[index++] = arr[i++]; } else { // 当前一个数组元素大于后一个数组元素时,累加逆序对 // s[i] > s[j] -> s[i]...s[mid] > s[j] inverseNum += (mid - i + 1); temp[index++] = arr[j++]; } } while (i <= mid) { temp[index++] = arr[i++]; } while (j <= right) { temp[index++] = arr[j++]; } for (int k = 0; k < temp.length; k++) { arr[left++] = temp[k]; } return inverseNum; } }

编辑于 2017-07-28 15:08:55 回复(4)
啊啊
发表于 2022-05-07 23:30:26 回复(0)
# -*- coding:utf-8 -*-
class AntiOrder:
    def count(self, A, n):
        # write code here
        self.res = 0
        # 调用归并排序计算逆序数
        self.mergeSort(A)
        return self.res
    def mergeSort(self, A):
        if len(A) <= 1:
            return A     # 递归结束
        mid = len(A) // 2
        left = self.mergeSort(A[:mid])    # 左边排好序
        right = self.mergeSort(A[mid:])    # 右边排好序
        
        merged = []
        while left and right:
            if left[0] <= right[0]:
                merged.append(left.pop(0))
            else:
                self.res += len(left)    # 逆序数
                merged.append(right.pop(0))
        # 剩余部分放在数组后面
        merged.extend(right if right else left)
        return merged


发表于 2020-12-13 13:25:33 回复(0)