TreeSet的优点和局限性

TreeSet是二叉查找树，它可以完成一些操作：快速查找某个数，查找小于某个数的个数，查找大于某个数的个数
但是Java的标准库TreeSet有一些限制，即它不能存放重复的元素，这就导致了一些局限性。

一个剑指Offer题目----数组中的逆序对数

给定一个数组a，数组长度为n(n>=2)，求这个数组中逆序的元素对数。两个元素逆序是指对于 i<j, a[i]>a[j]。

解法：记f(i)为数组a中a[0 ~ i]中所有大于a[i]的数目个数，则显然逆序对数就等于
f(0)+f(1)+....+f(n-1)

怎么求f(i)？

对于a[0 ~ i]，我们将其排序，然后使用二分查找，就可找到a[i]的位置，通过统计a[i]右侧元素的个数，求得f(i)。
但是注意到求f(i+1)和求f(i)之间的联系：都要求子数组排序，而a[0 ~ i+1]和a[0 ~ i]相比仅仅增加了一个元素。所以很明显，求f(i)是求f(i+1)的子问题。
现在假设a[0 ~ i]已经排序， 怎么插入a[i+1]使得序列保持有序且效率最高？显然TreeSet就是我们所需要的数据结构。使用数组插入排序的复杂度是O(n), 而使用TreeSet只需要O(logn)。唯一的不足是，数组中有重复元素，TreeSet不允许重复，因此无法有效统计出小于某个数的所有元素的个数。
一个可行的选择是使用允许重复的Google集合框架，MultiSet。但是在仅仅使用标准库的限制下 ，可以使用下面介绍得Trick。

引入重复元素的方法

核心思想：将待存入TreeSet的元素包装起来，自定义比较器；通过特殊的标记来确定某个元素值的左右边界。
包装元素： 原来需要存入整数i， 包装成元素对的形式。简言之，就是通过存入<i,-1> 表示元素的左边界， <i,1>表示元素的右边界, <i,0>表示存入元素的左右边界之间。元素的左右边界均只能有一个，为了统计元素右边的值的个数，优先放入右边界，然后是左边界，多余的放入中间部分。
实现自定义的Comparator：显然对于<i,s0> <j,s1> ， 若i,j不相同，顺序就是i,j的顺序；否则若i=j, 若s0==s1==0, 表明这两个元素不是边界，则它们必须返回非0值表示不相等，这是存储重复元素的关键所在，也是被称为Trick的原因。

伪代码：

     // 通过这个方法来获取一个TreeSet， 主要自定义了一个比较器
    newTreeSet()：
        return new TreeSet(new Comparator<int[]>{()
            compare(int[] a,int[] b)
            {
                if a[0]!=b[0]
                    return a[0]-b[0]
                if a[1]==0 && b[1]==0:
                    return 1;//所有边界内部的值都应当视为不同的。此处也可以随机返回非0值，也可以
                             //间隔返回值，比如在-1,1之间切换，也就是说initValue=1, return initValue=-
                              //initValue; 这样添加可以减少内部的调整次数。
                return a[1]-b[1];
            }
        
        })
      //定义添加元素的操作, 优先添加右边界，然后左边界，其他情况添加到边界内部
    addElement(treeSet, e)：
        if <e,1> not exists
            add  it
            return
        if <e,-1> not exists
            add it
            return
        add <e,0>

      // 计算逆序对数
    reversedOrders(a)：
        TreeSet<int[]>  set=newTreeSet();
        sum=0
        addElement(set,a[0]);
        for k=1 to a.length-1:
            int[] data=new int[]{a[k],1};
            sum+=set.tailSet(data,false).size() //大于a[k]的元素的个数
            addElement(set,a[k]);
        return sum
    

Java代码：

import java.util.Comparator;
import java.util.TreeMap;
import java.util.TreeSet;

public class MultiTreeSet {
    
    public static TreeSet<int[]> newTreeSet()
    {
        return new TreeSet<int[]>(new Comparator<int[]>() {

            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]!=o2[0])
                    return o1[0]-o2[0];
                if(o1[1]==0 && o2[1]==0)
                    return 1;
                return o1[1]-o2[1];
            }
        });
    }
    
    public static void addElement(TreeSet<int[]> set,int[] data)
    {
        data[1]=1;
        if(!set.contains(data))
        {
            set.add(data);return;
        }
        data[1]=-1;
        if(!set.contains(data))
        {
            set.add(data);return;
        }
        data[1]=0;
        set.add(data);
    }
    public static void addElement(TreeSet<int[]> set,int i)
    {
            addElement(set, new int[]{i,0});
    }
    
    //展示如何使用扩展的TreeSet
    public static void demo()
    {
        TreeSet<int[]> treeSet=newTreeSet();
        int[] arr=new int[]{1,2,3,3,4,6,7};
    
        for(int i:arr)
            addElement(treeSet, i);
        System.out.println(treeSet);
        System.out.println(treeSet.tailSet(new int[]{3,1},false).size());
        System.out.println(treeSet.headSet(new int[]{3,-1},false).size());
    }
    
    public static int reversedOrderPairs(int[] arr)
    {
        TreeSet<int[]> set=newTreeSet();
        int sum=0;
        addElement(set, arr[0]);
        for(int i=1;i<arr.length;i++)
        {
            int[] data=new int[]{arr[i],1};
            sum+=set.tailSet(data, false).size();
            addElement(set, data);
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] arr=new int[]{
            4,5,6,2,9,2,10,32,10,5
        };// 结果是13
        System.out.println("desired result is :"+13);
        System.out.println("returned result is :"+reversedOrderPairs(arr));// 输出13, 正确
    }
}