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, 正确
}
}
