合集算法

输入: [[1,5],[3,7],[8,10],[15,20]]
输出: [1,7]

分析问题:
1.数组内部数据可能是乱序,需要排序
2.输入的多个数组可能是乱序,需要排序
3.多个数组,可能有多个合集,或者多个数组是一个大合集


针对问题1:
使用:Collections.sort进行数组内排序

针对问题2:
使用 Collections.sortc重写compare方法,以数组内最大值,把多个数组从小到大进行排序

1. 把指定数组在数组池中是否有合集,把最终合集结果写入对象中,且该对象有对应计数器判断,数组池中有几个可合集数组
2. 重写对象中的equals方法和hashCode方法,采用hashSet去重方式,可得到数组池中 多个合集、单个合集的结果


/**
  * 判断合集,若输入的合集,通过计数器形式,判断指定数组在多个数组列表中是否有 合集对象
  * @param resultLists
  * @param checkList
  * @return
  */
 private HejiCountObj hejiCheckList(List<List> resultLists , List<Integer> checkList){
     int count = 0;

     for(List<Integer> tempList :resultLists){
         if(checkMaxIntegerInNextList(checkList,tempList)){
             count ++;
             checkList = Lists.newArrayList(minInterger(checkList),maxInterger(tempList));
             System.out.println(checkList);
         }
     }
     return new HejiCountObj(checkList,count,minInterger(checkList),maxInterger(checkList));
 }

 /**
  * 判断两个排序完成的数组是否为合集
  * @param list
  * @param listNext
  * @return
  */
 private boolean checkMaxIntegerInNextList(List<Integer> list, List<Integer> listNext){

     if(maxInterger(list) >= minInterger(listNext) && maxInterger(list) <= maxInterger(listNext)){
         return true;
     }

     return false;
 }


 /**
  * 多个数组list,从小到大进行排序
  * @param alllists
  * @return
  */
 private List<List> sortAllList(List<List> alllists){

     Collections.sort(alllists, new Comparator<List>() {
         @Override
         public int compare(List o1, List o2) {
             return maxInterger(o1).compareTo(maxInterger(o2));
         }
     });
     return alllists;
 }

 /**
  * 获取数组最小值
  * @param integerList
  * @return
  */
 private Integer maxInterger(List<Integer> integerList){
     return Collections.max(integerList);
 }

 /**
  * 获取数组最大值
  * @param integerList
  * @return
  */
 private Integer minInterger(List<Integer> integerList){

     return Collections.min(integerList);
 }

 /**
  * 数组排序
  * @param integerList
  * @return
  */
 private List<Integer> sortList(List<Integer> integerList){

     Collections.sort(integerList);

     return integerList;
 }

实现内部排序及多个数组整体排序


        List<List> lists = Lists.newArrayList();

//        List list1 = sortList(Lists.newArrayList(1,3));
//        List list2 = sortList(Lists.newArrayList(6,2));
//        List list3 = sortList(Lists.newArrayList(10,8));
//        List list4 = sortList(Lists.newArrayList(15,20));

//        List list1 = sortList(Lists.newArrayList(1,3));
//        List list2 = sortList(Lists.newArrayList(6,2));
//        List list3 = sortList(Lists.newArrayList(10,8));
//        List list4 = sortList(Lists.newArrayList(9,12));


        List list1 = sortList(Lists.newArrayList(1,3));
        List list2 = sortList(Lists.newArrayList(6,2));
        List list3 = sortList(Lists.newArrayList(10,8));
        List list4 = sortList(Lists.newArrayList(9,12));
        List list5 = sortList(Lists.newArrayList(7,4));
        lists.add(list2);
        lists.add(list1);
        lists.add(list3);
        lists.add(list4);
        lists.add(list5);

        List<List> resultLists = sortAllList(lists);
        System.out.println(resultLists);


        List<List> checkResultList = Lists.newArrayList();

        HejiCountObj hejiCountObj = hejiCheckList(resultLists,list1);

        System.out.println(hejiCountObj.getCheckList());
        System.out.println(hejiCountObj.getCount());

        List<HejiCountObj> hejiCountObjList = Lists.newArrayList();
        //采用HashSet进行对象去重
        Set<HejiCountObj> hashSet = new HashSet<HejiCountObj>();

        for(int i = 0; i < resultLists.size(); i++){
            hejiCountObj = hejiCheckList(resultLists,resultLists.get(i));

            if(hejiCountObj.getCount() == resultLists.size()){
                hashSet.add(hejiCountObj);
                break;
            }

            if(hejiCountObj.getCount() == 0 || hejiCountObj.getCount() == 1){
                continue;
            }

            hashSet.add(hejiCountObj);
        }


        Iterator iterator = hashSet.iterator();

        while (iterator.hasNext()){

            HejiCountObj hejiCountObj1 = (HejiCountObj) iterator.next();

            checkResultList.add(hejiCountObj1.getCheckList());
        }

        System.out.println(checkResultList);

重新排序结果: [[1, 3], [2, 6], [4, 7], [8, 10], [9, 12]]
最终合集结果: [[1, 7], [8, 12]]

重写对 List 内数组相同的定义

package com.finger.test.temp;

import java.util.List;

/**
 * @Des:
 * @Auther: 飞狐
 * @Date: 2019/1/4
 */
public class HejiCountObj {

    //进行确认的数组结果集
    private List<Integer> checkList;

    //匹配的次数
    private int count = 0;

    private Integer minInteger;

    private Integer maxInteger;

    public HejiCountObj(List<Integer> checkList, int count, Integer minInteger, Integer maxInteger) {
        this.checkList = checkList;
        this.count = count;
        this.minInteger = minInteger;
        this.maxInteger = maxInteger;
    }

    public Integer getMinInteger() {
        return minInteger;
    }

    public void setMinInteger(Integer minInteger) {
        this.minInteger = minInteger;
    }

    public Integer getMaxInteger() {
        return maxInteger;
    }

    public void setMaxInteger(Integer maxInteger) {
        this.maxInteger = maxInteger;
    }

    public List<Integer> getCheckList() {
        return checkList;
    }

    public void setCheckList(List<Integer> checkList) {
        this.checkList = checkList;
    }

    public int getCount() {
        return count;
    }

    public void setCount(int count) {
        this.count = count;
    }

    @Override
    public boolean equals(Object obj){
        HejiCountObj hejiCountObj = (HejiCountObj)obj;

        return this.maxInteger.equals(hejiCountObj.getMaxInteger());

    }


    @Override
    public int hashCode(){
        return maxInteger.hashCode();
    }

}

不清楚是否还有更加简单的方法进行处理


↙↙↙阅读原文可查看相关链接,并与作者交流