首页 文章

对整数的ArrayLists的ArrayList进行排序,其中内部列表具有不同的长度

提问于
浏览
0

Ques: 给定一组不同的整数S,返回所有可能的子集 . 子集中的元素必须按非降序排列 . 此外,子集应按升序(词典)顺序排序 .
My Approach: 我先输入了输入 . 然后找到所有子集并将每个步骤中找到的新子集附加到"res" . 现在我尝试使用自定义比较器对"res" arraylist进行排序 . 但输出出错了 .
对于输入arraylist a={ 15, 12, 4 }
输出: res={ {}, {4}, {4,12}, {4,15}, {4,12,15}, {12}, {12,15}, {15} }
预期产出: res={ {}, {4}, {4,12}, {4,,12,15}, {4,15}, {12}, {12,15}, {15} }

public static ArrayList<ArrayList<Integer>> subsets(ArrayList<Integer> a) 
{   int i,j;
    ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
    ArrayList<Integer> temp;
    res.add(new ArrayList<Integer>());        
    Collections.sort(a);   
    for(i=0;i<a.size();i++)
    {   ArrayList<ArrayList<Integer>> str=new ArrayList<ArrayList<Integer>>();
        for(ArrayList<Integer> al:res)
        {   temp=new ArrayList<Integer>();
            temp.addAll(al);
            temp.add(a.get(i));             
            str.add(temp);
        }
        res.addAll(str);

    }
    Collections.sort(res,new Comparator<ArrayList<Integer>>()
    {   public int compare(ArrayList<Integer> p,ArrayList<Integer> q)
        {   if(q.size()==0)
                return 1;
            else                        
                return Integer.compare(p.get(0),q.get(0));
        }
    });
    return res;
}

为了对内部列表进行相互排序,我写了这个比较器 . 但比较者给出了错误的答案 . 我想我的比较器编写错误 .

2 回答

  • 0

    您不应该仅仅比较列表的第一个元素 . 将两个列表与相同的第一个元素进行比较时会发生什么,但是后面有任意数量的不同元素?

    要缓解此问题,您必须比较每个元素,直到达到差异 . 我建议如下:

    int oneSize = listOne.size();
    int twoSize = listTwo.size();
    
    for(int i = 0; i < oneSize; i++)
    {
        if(i == oneSize || i == twoSize)
            return oneSize - twoSize;
    
        int elementOne = listOne.get(i);
        int elementTwo = listTwo.get(i);
        if(elementOne == elementTwo)
           continue;
    
        return Integer.compare(elementOne, elementTwo);
    }
    
  • 1

    您需要先单独对内部列表进行排序,然后对外部列表进行排序 .

    下面的代码片段对我有用 .

    Collections.sort(res, new Comparator<List<Integer>>() {
    
                @Override
                public int compare(List<Integer> p, List<Integer> q) {
    
                    Collections.sort(p);
                    Collections.sort(q);
    
                    return Integer.compare(p.get(0),q.get(0));
                }
            });
    

    Output:

    Before Sorting
    [12, 15] 
    [25, 15] 
    [10, 12, 25] 
    After Sorting 
    [10, 12, 25] 
    [12, 15] 
    [15, 25]
    

    Edit:

    请找到适用于我的以下代码 .

    public class Stack1 {
    
        private List<List<Integer>> outerList = null;
        private List<Integer> innerList = null;
    
        public static void main(String args[]) {
            Stack1 stack1 = new Stack1();
    
            List<Integer> fullList = new ArrayList<>();
            fullList.add(15);
            fullList.add(12);
            fullList.add(4);
    
            stack1.subsetsOfList(fullList);
    
            System.out.println("Before Sorting");
            stack1.printLists();
            stack1.sortLists();
            System.out.println("After Sorting");
            stack1.printLists();
        }
    
        public void subsetsOfList(List<Integer> a) {
            int i, j;
            outerList = new ArrayList<>();
            outerList.add(new ArrayList<Integer>());
            Collections.sort(a);
            for (i = 0; i < a.size(); i++) {
                List<List<Integer>> str = new ArrayList<>();
                for (List<Integer> al : outerList) {
                    innerList = new ArrayList<>();
                    innerList.addAll(al);
                    innerList.add(a.get(i));
                    str.add(innerList);
                }
                outerList.addAll(str);
            }
        }
    
        public void printLists() {
            for (List<Integer> list : outerList) {
                System.out.println(list);
            }
        }
    
        public void sortLists() {
            Collections.sort(outerList, new Comparator<List<Integer>>() {
                @Override
                public int compare(List<Integer> t, List<Integer> t1) {
    
                    Collections.sort(t);
                    Collections.sort(t1);
    
                    for(int i = 0; i < t.size(); i++) {
                        if(t.size() > i && t1.size() > i) {
                            int result = Integer.compare(t.get(i), t1.get(i));
                            if(result != 0) {
                                return result;
                            } 
                        } else if (t.size() > i && t1.size() < i) {
                            return 1;
                        } else if (t.size() < i && t1.size() > i) {
                            return -1;
                        }
                    }
    
                    return 0;
                }
            });
        }
    }
    

    Ouput:

    Before Sorting
    []
    [4]
    [12]
    [4, 12]
    [15]
    [4, 15]
    [12, 15]
    [4, 12, 15]
    After Sorting
    []
    [4]
    [4, 12]
    [4, 12, 15]
    [4, 15]
    [12]
    [12, 15]
    [15]
    

相关问题