当前位置:首页 > 开发 > 编程语言 > Java > 正文

利用线段树求逆序数(JAVA)

发表于: 2012-12-04   作者:128kj   来源:转载   浏览:
摘要:    设A[1…n]是一个包含n个不同数的数组。如果在i<j的情况下,有A[i]>A[j],则(i,j)就称为A中的一个逆序对(inversion)    现给出一个数列,求该数列中的逆序对数(逆序数)。最直接的暴力方法;   两层for循环就可以算出来逆序数:每遇到一个元素回头遍历寻找比其大的元素个数即可,   当
   设A[1…n]是一个包含n个不同数的数组。如果在i<j的情况下,有A[i]>A[j],则(i,j)就称为A中的一个逆序对(inversion)

   现给出一个数列,求该数列中的逆序对数(逆序数)。最直接的暴力方法;
  两层for循环就可以算出来逆序数:每遇到一个元素回头遍历寻找比其大的元素个数即可,
  当然向后寻找比其小的元素个数也可以,复杂度为O(n^2),代码:

   int sum = 0;
   for(int i = 0; i < size; ++i) {
      for(int j = i+1; j < size; ++j){
         if(arr[i] > arr[j]){
             ++sum;
         }
     }
  }
  return sum;


下面方法用线段树,逆序数就是一个“区间和”的问题:
对于数列中的每个元素,它对应的逆序数便是之前序列中大于该元素的元素个数和。

由于线段树的插入和查询操作皆可以在lgn的时间内完成,故遍历一个数列求逆序数的时间复杂度为O(nlgn)

例:HDU1394
    给你一个数字组成的序列,然后进行这样的操作,每次将最前面一个元素放到最后面去会得到一个序列,
那么这样就形成了n个序列,那么每个序列都有一个逆序数,找出其中最小的一个输出!
样例:
Sample Input
10
1 3 6 9 0 8 5 7 4 2
Sample Output
16

分析:

线段树节点这样定义:
class Seg_Tree {//线段树节点
int left,right;
        int val;//区间内已插入的节点数
int calmid() {
return (left+right)/2;
}
   }

先以区间[0,9]为根节点建立val都为0的线段树, 
  
再看看怎样求下面序列的逆序数:
1 3 6 9 0 8 5 7 4 2
在线段树中插入1, 插入之前先询问区间[1,9]已插入的节点数(如果存在,必与1构成逆序)  v1=0
在线段树中插入3, 插入之前先询问区间[3,9]已插入的节点数(如果存在,必与3构成逆序)  v2=0
在线段树中插入6, 插入之前先询问区间[6,9]已插入的节点数(如果存在,必与6构成逆序)  v3=0
在线段树中插入9, 插入之前先询问区间[9,9]已插入的节点数(如果存在,必与9构成逆序)  v4=0
在线段树中插入0, 插入之前先询问区间[0,9]已插入的节点数(如果存在,必与0构成逆序)  v5=4
在线段树中插入8, 插入之前先询问区间[8,9]已插入的节点数(如果存在,必与8构成逆序)  v6=1
在线段树中插入5, 插入之前先询问区间[5,9]已插入的节点数(如果存在,必与5构成逆序)  v7=3
在线段树中插入7, 插入之前先询问区间[7,9]已插入的节点数(如果存在,必与7构成逆序)  v8=2
在线段树中插入4, 插入之前先询问区间[4,9]已插入的节点数(如果存在,必与4构成逆序)  v9=5
在线段树中插入2, 插入之前先询问区间[2,9]已插入的节点数(如果存在,必与2构成逆序)  v10=7
累加v1+……+v10  =22,这就是1 3 6 9 0 8 5 7 4 2的逆序数了.


这题要把第一个数放到最后
3 6 9 0 8 5 7 4 2 1
这样就增加了9个逆序,其逆序为22+9=31
6 9 0 8 5 7 4 2 1 3
这样增加了6个,减少了3个,其逆序数为31+6-3=34;
............
//公式:第一个数移到最后位置后逆序数
//sum=sum+(-low[a[i]]+up[a[i]]),low[a[i]]表示比a[i]小的数
//在0-(n-1)序列里low[a[i]]=a[i],up[a[i]]=n-a[i]-1;

最后AC过的代码:



 import java.util.Scanner;

     class Seg_Tree {//线段树节点
	int left,right;
        int val;//区间内已插入的节点数
	int calmid() {
		return (left+right)/2;
	}
   }

  public class Main{
     private int LL(int x) { return x<<1;}  //两倍;
     private int RR(int x) { return x<<1|1;} //两倍+1;
     Seg_Tree tt[];
 

    public Main(){
      tt=new Seg_Tree[16370];//用数组实现线段树
      for(int i=0;i<16370;i++)
          tt[i]=new Seg_Tree();
    }

    private void build(int left,int right,int idx) {//构建一棵val值全为0的线段树
	tt[idx].left = left;
	tt[idx].right = right;
	tt[idx].val = 0;
	if(left == right) return ;	
	int mid = tt[idx].calmid();
	build(left,mid,LL(idx));
	build(mid+1,right,RR(idx));
    }
   
   /*  如果将节点全部插入,应该是下面结果:
     C:\java>java Main
     10
     1 3 6 9 0 8 5 7 4 2
   [0,0]=.val=1 [0,1].val=2  [1,1].val=1  [0,2].val=3  [2,2].val=1  [0,4].val=5  [3,3].val=1  
    [3,4].val=2  [4,4].val=1  [0,9].val=10  [5,5].val=1  [5,6].val=2  [6,6].val=1  
    [5,7].val=3  [7,7].val=1  [5,9].val=5  [8,8].val=1  [8,9].val=2  [9,9].val=1
   */
    
   private void insert(int aim,int l,int r,int k){  //将aim插入到线段树
    if(tt[k].left==aim&&tt[k].right==aim) {
      tt[k].val++;return ;
    }  
  
    if(aim<=tt[k].calmid()) 
       insert(aim,l,tt[k].calmid(),LL(k));  
    else     
      insert(aim,tt[k].calmid()+1,r,2*k+1);  
    tt[k].val=tt[LL(k)].val+tt[RR(k)].val;  
  }  

    public void printTree(int i){//中序遍历线段树
      if(2*i>16370) return;
      printTree(2*i);
      if(tt[i].right!=0) System.out.print("["+tt[i].left+","+tt[i].right+"]"+".val="+tt[i].val+"  ");//注意,没有输出[0,0]
      printTree(2*i+1);
      
    }
       
  
   

    //查询[left,right]中已插入的节点数
    private int query(int left,int right,int idx){
	if(left == tt[idx].left && right == tt[idx].right) 
           return tt[idx].val;
	
	int mid = tt[idx].calmid();
	if(right <= mid){
		return query(left,right,LL(idx));
	} 
       else if(mid < left) {
		return query(left,right,RR(idx));
	} 
       else {
		return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx));
	}
     }


  

     public static void main(String[] args){
        Scanner in=new Scanner(System.in);
	int n;
	while(in.hasNext()) {
          n=in.nextInt();
          Main ma=new Main();
          int val[]=new int[n];
	  ma.build(0,n-1,1);
	  int sum = 0;	
          for(int i=0;i<n;i++){
            val[i]=in.nextInt();
            sum += ma.query(val[i],n-1,1);//先查询
            ma.insert(val[i],0,n-1,1);//后插入
	   }
         // ma.printTree(1);
         // System.out.println();//中序遍历线段树
        //  System.out.println(sum);
	   int ret = sum;
	
        for(int i=0;i<n;i++){
	  sum = sum - val[i] + (n - val[i] - 1);
	  ret=Math.min(ret,sum);
	}
	 System.out.println(ret);
         
	}
       
   }
}



源码:

利用线段树求逆序数(JAVA)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目链接:http://poj.org/problem?id=2299 Description In this problem, you have to analyze a p
Buy Tickets Time Limit:4000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Description
#include <stdio.h> int main ( ) { int n,a[1000],s,t,k,i=0,j; scanf("%d",&n); while(n>
Ultra-QuickSort Time Limit: 7000MS Memory Limit: 65536K Total Submissions: 44554 Accepted: 16
覆盖的面积 Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
点到直线的距离可以直接做垂线求取,但线段是有首尾点的,若要求距离则要考虑首尾点。 点和线段的关
定义 线段树是一种的二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应
树结构的基本思想是分割。普通二叉搜索树是按对象来进行划分,效果往往和数据结构内对象有关;而线
线段树的构造思想 线段树是一棵二叉树,树中的每一个结点表示了一个 区间[a,b]。每一个叶子节点表示
线段树在一些acm题目中经常见到,这种数据结构主要应用在计算几何和地理信息系统中。下图就为一个线
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号