给定数组，求出数组每个数左边比该数小的数的个数

一时失言乱红尘 2022-10-02 11:56 141阅读 0赞

# 给定数组，求出数组每个数左边比该数小的数的个数 #

## 1.问题描述 ##

给定一个数组num,数组长度为n,求出数组中每个数左边比该数小的数的个数

## 2.做法 ##

是一道比较典型的线段树的题目．

具体做法是我们以数组中最小的数low和最大的数high为线段树根节点的两个端点，建立线段树，线段树所有节点的权值初始为空.

接着在线段树中依次查询数组中的数x，找到相应的位置．找到后，权值+1，并向上改变父节点的权值，这里是为了统计数组中落在\[l,r\]区间的数的个数．

最后求解答案时我们只需要在线段树中寻找\[low,x-1\]节点的值就好，具体过程参考代码（java实现）

import java.util.ArrayList;
    import java.util.Scanner;
    
    public class Main {
        
        public static int a;
        public static int b;
        public static int c;
        final static int INF = 0xffffff;
        final static int LOW = -0xfffffff;
        public static class SegmentTreeNode {
        
            SegmentTreeNode leftChild;
            SegmentTreeNode rightChild;
            public int count;
            public int left;
            public int right;
            public int cover;
            public SegmentTreeNode(int left, int right) {
        
                this.left = left;
                this.right = right;
                this.count = 0;
                this.cover = 0;
            }
        }//java线段树的实现
    
        public static void build(SegmentTreeNode root){
        //建立线段树
            int left = root.left;
            int right = root.right;
            if(left >= right){
        
                return;
            }else{
        
                int mid = (left + right) / 2;
                SegmentTreeNode l = new SegmentTreeNode(left,mid);
                SegmentTreeNode r = new SegmentTreeNode(mid + 1,right);
                root.leftChild = l;
                root.rightChild = r;
                build(l);
                build(r);
            }
        }
    
        public static void modfy(SegmentTreeNode root,int index){
        //查找数字的位置
            int left = root.left;
            int right = root.right;
            int mid = (left + right)/2;
            if ( left == right){
        
                root.count += 1;
                return;
            }
            if(left > right){
        
                return;
            }
            if(index <= mid){
        
                modfy(root.leftChild,index);
            }else if(index > mid){
        
                modfy(root.rightChild,index);
            }
            root.count = root.leftChild.count + root.rightChild.count;
        }
    
        public static int quarry(SegmentTreeNode root,int start,int end){
        //进行查询
            if (start > end || root.left > root.right){
        
                return 0;
            }
            if(start <= root.left && end >= root.right){
        
                return root.count;
            }
            int mid = (root.left + root.right) / 2;
            if (start > mid){
        
                return quarry(root.rightChild ,start ,end);
            }else if(end < mid + 1){
        
                return quarry(root.leftChild ,start ,end);
            }else{
        
                return (quarry(root.leftChild ,start ,mid) + quarry(root.rightChild,mid+1,end));
            }
        }
    
        public static void init(){
        
            Scanner input = new Scanner(System.in);
            int n = input.nextInt();
            int min = INF;
            int max = LOW;
            int[] num = new int[n];
            for (int i = 0;i < n;i++){
        
                num[i] = input.nextInt();
                min = Math.min(min,num[i]);
                max = Math.max(max,num[i]);
            }
            SegmentTreeNode root = new SegmentTreeNode(min,max);
            build(root);
            for (int i = 0;i < n;i++){
        
                modfy(root,num[i]);
                int s = quarry(root,min,num[i]-1);
                if (i != n-1)
                    System.out.print(s+" ");
                else
                    System.out.println(s);
            }
        }
    
        public static void main(String[] args){
        
            init();
        }
    }