按照子列表中第一个数字排序List<List<Integer>>

Question

按照子列表中第一个数字排序List<List<Integer>>

3

我是一名有用的助手，可以为您翻译文本。

我遇到了以下问题。我有一个ArrayList(1)，其中包含ArrayLists(2)。我需要做的是将结构排序，以便ArrayLists(2)的第一个元素按升序排列下降ArrayList(1)。澄清一下：

输入：

3, 8, 6
2, 14, 205, 44, 1
1, 3

输出：

1, 3
2, 14, 205, 44, 1
3, 8, 6

请看它如何仅基于第一个值对行进行排序。

目前，我所定义的数组列表是由数组列表组成的：

List<List<Integer>> graph = new ArrayList<List<Integer>>();
// and I add elements to it likewise
graph.get(currentIndex).add(new ArrayList<Integer>());

我使用ArrayList的原因是因为我读到它比LinkedList更节省内存，而且我正在构建一个图的邻接列表。其中节点数或每个节点的邻接列表长度都可能不同。一行的第一个元素是start_node，其后是其相邻的节点。请问如何实现此排序？

- KDX2

更节省内存 - 尝试了解LinkedList的优点。对于邻接表，您应该使用LinkedList。 - oleg.cherednik

1

你可以将List包装在一个对象中，然后实现Comparable接口。在其中，你可以实现你的逻辑。此外，LinkedList的缓存局部性较差，因此由于内存分配不连续，可能会导致性能下降。 - MathBunny

3个回答

1

要比较两个子列表，您需要找到第一个不相等的对，并比较它们的值（如果两个都以类似于 32 的方式开头，则需要查看下一个值）。

List<List<Integer>> graph = new ArrayList<>();
graph.add(Arrays.asList(3, 8, 6));
graph.add(Arrays.asList(2, 14, 205, 44, 1));
graph.add(Arrays.asList(2, 14, 205, 44, 2));
graph.add(Arrays.asList(1, 3));
graph.add(Arrays.asList(1, 4));
graph.add(Arrays.asList(1, 4));
graph.add(Arrays.asList(1, 4, 5));

graph.sort((o1, o2) -> {
    int indice, cmp, min;
    for (indice = 0, min = Math.min(o1.size(), o2.size());
         indice < min; indice++) {
        if ((cmp = Integer.compare(o1.get(indice), o2.get(indice))) != 0) {
            return cmp;
        }
    }
    if (indice == o1.size()) return -1;
    if (indice == o2.size()) return 1;
    return 0;
});

System.out.println(graph);

[[1, 3], 
 [1, 4], 
 [1, 4], 
 [1, 4, 5], 
 [2, 14, 205, 44, 1], 
 [2, 14, 205, 44, 2], 
 [3, 8, 6]]

作为替代方案，另一种使用 Comparator 接口的方式（我同意这不是很好），它会比较值，直到其中一个列表为空，然后如果达到完全比较一个列表的大小。

graph.sort((o1, o2) -> {
    Comparator<List<Integer>> cc = Comparator.comparingInt(l -> l.get(0));
    int indice, min;
    for (indice = 0, min = Math.min(o1.size(), o2.size()); indice < min; indice++) {
        final int i = indice;
        cc = cc.thenComparingInt(l -> l.get(i));
    }
    return cc.thenComparingInt(List::size).compare(o1, o2);
});

- azro

如果o1等于o2或其中一个是另一个的前缀，则会出现越界异常。 - Matt Timmermans

@azro，我尝试了你提供的两种解决方案。最后的两个if语句的意思是，如果到目前为止两个列表中的所有元素都相等，则返回较小的那个，即长度更短的那个？我的输入是2 4 | 1 3 | 5 47 99，我希望前两个数字交换顺序。排序后输出：[] [] [2, 4, 1, 5, 5, 47, 99]。我尝试过使用ArrayList和LinkedList - 结果相同。 - KDX2

0

所以，这是我想出来的另一个解决方案。

思路是：使用Collections类的静态方法sort()，将列表的引用和一个由我们定义的compare()方法构成的新的Comparator对象传递给它。

Collections.sort(graph, new Comparator<List<Integer>>(){
@Override
public int compare(List<Integer> aList1, List<Integer> aList2) {
   return aList1.get(0).compareTo(aList2.get(0));
}
}));

- KDX2

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MyStackRunnethOver · Accepted Answer

据我理解，您希望按每个嵌套列表的第一个元素对顶级列表进行排序。是这样吗？以下是我如何处理：

List<List<Integer>> graph = new ArrayList<List<Integer>>();
// add a bunch of things ...
// ...

// Now, to sort:
graph.sort((x,y) -> Integer.compare(x.get(0), y.get(0)));

这里使用Integer获取Comparator，这就是sort()方法需要的以某些自定义标准进行排序的方式。在这种情况下，我们告诉它按照正常比较Integer的方式来比较graph中任意两个项目的第一个项，从而对List of Lists graph进行排序。

请注意，这假定graph中的所有项目都具有第一项。