要求：将连续数的数分成一组，不连续的分成另一组。如1、2、3、5、7、8，输出1-3、5-5、7-8。
方法一、不推荐
Bean对象保存分组的最大值和最小值。并提供将某数增加到该分组的方法。代码如下：
public class Bean
{
private int minValue;
private int maxValue;
public boolean add(int value)
{
if (value >= minValue && value <= maxValue)
{
// 已经存在该区间内，do nothing
return true;
}
if (value == minValue - 1)
{
// 比最小值小1，拓展最小值
minValue = value;
return true;
}
if (value == maxValue + 1)
{
// 比最大值大1，则拓展最大值
maxValue = value;
return true;
}
// 其他情况都增加该区间失败
return false;
}
public int getMinValue()
{
return minValue;
}
public void setMinValue(int minValue)
{
this.minValue = minValue;
}
public int getMaxValue()
{
return maxValue;
}
public void setMaxValue(int maxValue)
{
this.maxValue = maxValue;
}
}
BeanList类为List集合的简单封装。对外也提供将数字加入到某分组的方法，由于加入某个数字，可能会将两个分组合并成一个分组，如原来1-3和5-6组，加入4后，必须合并为1-6组，如下方法实现逻辑：如果某一个数字加入两个分组成功，则这两个分组可以合并。
public class BeanList
{
private List<Bean> beanList = new ArrayList<Bean>();
public void add(int value)
{
Bean existBean = null;
for (Bean bean : beanList)
{
if (bean.add(value))
{
if (existBean != null)
{
// 增加一个数据最多使两个区间合并
merge(bean, existBean);
return;
}
existBean = bean;
}
}
if (existBean == null)
{
addIfNotExist(value);
}
}
private void addIfNotExist(int value)
{
Bean bean = new Bean();
bean.setMinValue(value);
bean.setMaxValue(value);
beanList.add(bean);
}
private void merge(Bean existBean, Bean deleteBean)
{
if (existBean.getMaxValue() == deleteBean.getMinValue())
{
existBean.setMaxValue(deleteBean.getMaxValue());
beanList.remove(deleteBean);
}
else if (existBean.getMinValue() == deleteBean.getMaxValue())
{
existBean.setMinValue(deleteBean.getMinValue());
beanList.remove(deleteBean);
}
}
public void print()
{
for (Bean bean : beanList)
{
System.out.println(bean.getMinValue() + "======" + bean.getMaxValue());
}
}
}
测试类。BeanList只是简单将结果打印出来。
public class Test
{
public static void main(String[] args)
{
List<Integer> list = new ArrayList<Integer>();
list.add(8);
list.add(10);
list.add(9);
list.add(1);
list.add(3);
list.add(4);
list.add(5);
list.add(7);
list.add(6);
BeanList beanList = new BeanList();
for (Integer aa : list)
{
beanList.add(aa.intValue());
}
beanList.print();
}
}
性能测试：
public static void main(String[] args)结果： beanlist size [23094]
{
int max = 10000 * 10;
Random random = new Random();
BeanList beanList = new BeanList();
long startTime = System.currentTimeMillis();
for (int i = 0; i < max; i++)
{
beanList.add(random.nextInt(100000));
}
long endTime = System.currentTimeMillis();
System.out.println("count time [" + (endTime - startTime) + "] ms");
System.out.println("bean list size [" + beanList.getBeanList().size() + "]");
十万条数据，在十万内产生随机数，从结果来看参数了2.3W个区间，但是耗时为73秒。这个是相当慢的。
方法二：二分法
同样Bean
public class Bean implements Comparable<Bean>逻辑处理类BeanSearch。BeanSearch类同样也是List集合的简单封装。但是对外提供二个方法，一个是将区间增加到集合中，第二个方式用于将已经加入的集合的区间合并。因为加入一个数据到区间后马上合并是一个相当耗时的操作，很有必要提取出来。
{
private long start;
private long end;
/**
* <pre>
* 三种情况
* 1.如果other的结束区间比当前开始区间小，则返回1。
* 2.如果other的开始区间比当前结束区间大，返回-1.
* 3.其他情况表示两个区间有交集，返回0
*
* <pre>
*/
@Override
public int compareTo(Bean other)
{
if (other.end < this.start - 1)
{
return 1;
}
if (other.start > this.end + 1)
{
return -1;
}
return 0;
}
public void merge(Bean other)
{
// 将两个Bean区间合并
this.start = Math.min(this.start, other.start);
this.end = Math.max(this.end, other.end);
}
public long getStart()
{
return start;
}
public void setStart(long start)
{
this.start = start;
}
public long getEnd()
{
return end;
}
public void setEnd(long end)
{
this.end = end;
}
@Override
public String toString()
{
StringBuilder builder = new StringBuilder();
builder.append("Bean [start=");
builder.append(start);
builder.append(", end=");
builder.append(end);
builder.append("]");
return builder.toString();
}
}
public class BeanSearch性能测试：
{
private ArrayList<Bean> beanList = new ArrayList<Bean>();
/**
* 当前索引行
*/
private int current = -1;
/**
* 当前查询的参数Bean是否已经在区间集合beanList中存在
*/
private boolean isExist = false;
/**
* 如果isExist为true，则该值表示查询到的区间Bean
*/
private Bean searchedBean = null;
public BeanSearch()
{
}
public void add(long value)
{
Bean bean = new Bean();
bean.setStart(value);
bean.setEnd(value);
add(bean);
}
public void add(Bean bean)
{
binSearch(bean);
if (isExist)
{
searchedBean.merge(bean);
}
else
{
addIfNoExist(bean);
}
}
public void merge()
{
Bean bean = null;
Bean prevBean = null;
for (int i = beanList.size() - 1; i > 0; i--)
{
bean = beanList.get(i);
prevBean = beanList.get(i - 1);
if (prevBean.compareTo(bean) == 0)
{
prevBean.merge(bean);
beanList.remove(i);
}
}
}
public List<Bean> getBeanList()
{
return beanList;
}
private void binSearch(Bean bean)
{
int upper = beanList.size() - 1;
if (upper < 0)
{
// 集合中没有元素，则没有查询到，直接返回
isExist = false;
current = 0;
return;
}
int lower = 0;
while (true)
{
if (lower > upper)
{
isExist = false;
return;
}
current = (lower + upper) / 2;
searchedBean = beanList.get(current);
int result = searchedBean.compareTo(bean);
if (result == 0)
{
isExist = true;
return;
}
else if (result < 0)
{
lower = current + 1;
}
else if (result > 0)
{
upper = current - 1;
}
}
}
private void addIfNoExist(Bean bean)
{
int size = beanList.size();
if (size == 0)
{
beanList.add(bean);
return;
}
while (true)
{
int result = beanList.get(current).compareTo(bean);
if (result < 0)
{
if (current == size - 1)
{
// last one
beanList.add(bean);
return;
}
else if (beanList.get(current + 1).compareTo(bean) > 0)
{
current++;
beanList.add(current, bean);
return;
}
}
else if (result > 0)
{
if (current == 0)
{
// 已经是左侧第一位数据了,插入到第一行
beanList.add(0, bean);
return;
}
// 当前索引bean比参数bean大，则左移动一个进行比较
current--;
}
else
{
// result never equal zero
return;
}
}
}
}
@Test结果：
public void testAdd()
{
int max = 10000 * 100;
BeanSearch search = new BeanSearch();
Random random = new Random();
long startTime = System.currentTimeMillis();
for (int i = 0; i < max; i++)
{
long value = Math.abs(random.nextInt(1000000));
search.add(value);
}
search.merge();
long endTime = System.currentTimeMillis();
System.out.println("coust time [" + (endTime - startTime) + "] ms");
System.out.println("beanList size[" + search.getBeanList().size() + "]");
}
beanListsize[232698]
100W数据，在100W内产生随机数，共有23.2W个区间，但是耗时29秒。
为何差距这么大
在这两个方法中，都用相同的处理步骤，那就是根据当前区间查询可以融合的区间。在方法一种，依次对集合循环，那么10W条数据最坏的情况需要比较10W次，而其中很多都是多余的比较。这就是二分法的优点。
举个例子：1-100之间你猜一个数字，你猜中正确数字的次数。方法一是从1开始，依次猜，那么最差的情况需要猜100次，这是笨拙的。而方法二是第一次猜50，如果猜小了，那下次猜75，再次猜小了，那下次就猜83，最多7次可以猜到答案。这就是二分法的精髓所在，当然二分法要求数据是有序的，无序是没有意义的。在方法二中，将不存在的区间添加(addIfNotExist)就是有序添加。