在链表数组中查找最长链表

Question

我有一个链表数组(一个邻接表)，大多数链表的长度是4，但有一些将随机超过4。我的目标是遍历数组找到长度大于4的(这很简单)然后将索引添加到数组中例如

for (int i = 0; i < 1000; i++){
    if(sWorld[i].length > 4)
         //add i to an array
         // then sort the array

真的想不出该怎么做。我试图添加到一个链接列表，然后链接列表toArray()，但后来它搞砸了。我只是不知道如何添加'i'点在我的sWorld数组说的第一个位置在新的数组中，我将使用大于4的大小。

任何帮助将非常感激!

编辑澄清位

我需要size> 4的位置的索引，但我想知道我得到的索引中哪个是最大的。也许在我的op中我不是100%清楚，但基本上我试图找到数组中1000个索引中哪个有最多的连接(最长的链表)是有意义的?

我想知道数组的前10个连接索引(也就是哪10个链表的大小最大)

Answer 1

您可以使用ArrayList来存储索引:

List<Integer> indexes = new ArrayList<Integer>();
for (int i = 0; i < 1000; i++){
    if (sWorld[i].length > 4) {
         //add i to a list (not an array yet)
         indexes.add(i);
    }
    ...
}
// then sort the list
// not necessary, as indexes are inserted in the right order, but if you must...
// Collections.sort(indexes);
// and, if you need an array instead of a list
Integer[] indexesArray = indexes.toArray(new Integer[indexes.size()]);

List或ArrayList作为变长数组。虽然不如实际的数组有效。

如上所示，稍后不需要对数组进行排序，但是，如果必须这样做，可以使用Collections.sort()。

另外，如果你必须有一个int[]而不是Integer[]，请检查:如何转换列表在Java中int[] ?

更新:

当你想知道大数组的大小和索引时，这是一个全新的问题。下面是处理它的工作代码。

基本上，每次你发现一个数组的大小大于4，你添加一对(index, size)到列表。然后按大小降序排列该列表。

在main()方法的末尾，创建了一个数组(int[] topTenIndexes)，其中包含了10个最大数组的索引(索引按照数组长度降序排列)。当没有足够的大(长度> 4)数组时，结果是-1。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class Example {
    public static void main(String[] args) {
        List<ArrayIndexAndSize> indexes = new ArrayList<ArrayIndexAndSize>();
        int[][] sWorld = {{1},{2,5,5,5,5},{3,6,6,6,6,6}};
        for (int i = 0; i < sWorld.length; i++){
            if (sWorld[i].length > 4) {
                 // add a pair (index, size) to the list
                 indexes.add(new ArrayIndexAndSize(i, sWorld[i].length));
            }
            //...
        }
        // then sort the list by array SIZE, in descending order
        Collections.sort(indexes);
        // Print it!
        System.out.println(indexes);
        /* output:
        "[[Array index: 2; Array size: 6], [Array index: 1; Array size: 5]]"
         */
        // Generating an array with the top ten indexes
        int[] topTenIndexes = new int[10];
        Arrays.fill(topTenIndexes, -1);
        for (int i = 0; i < indexes.size() && i < 10; i++) {
            topTenIndexes[i] = indexes.get(i).index;
        }
        // Print it
        System.out.println(Arrays.toString(topTenIndexes));
        /* output: [2, 1, -1, -1, -1, -1, -1, -1, -1, -1] */
    }
    public static class ArrayIndexAndSize implements Comparable<ArrayIndexAndSize> {
        public int index;
        public int size;
        public ArrayIndexAndSize(int index, int size) {
            this.index = index;
            this.size = size;
        }
        /* Order by size, DESC */
        /* This is called by Collections.sort and defines the order of two elements */
        public int compareTo(ArrayIndexAndSize another) {
            int thisVal = this.size;
            int anotherVal = another.size;
            return -(thisVal<anotherVal ? -1 : (thisVal==anotherVal ? 0 : 1));
       }
        @Override
        public String toString() {
            return "[Array index: "+index+"; Array size: "+size+"]"; 
        }
    }
}

Answer 2

如果你有一个数组LinkedList<?>[] sWorld(填充你在?中使用的类型)，然后这样做:

ArrayList<Integer> listOfLists = new ArrayList<>();
for (int i=0; i<sWorld.size(); i++) {
    if (sWorld[i].size > 4) {
        listOfLists.add(i);
    }
}
Comparator<Integer> sizeComparator = new Comparator<Integer>() {
    public int compare(Integer a, Integer b) {
        return Integer.compare(sWorld[a].size(), sWorld[b].size());
    }
}
Collections.sort(listOfLists, sizeComparator);