java - 使用多个迭代器在Java中查找Arraylist的中间和第三个元素

Question

关于寻找中间元素已经存在一些问题。

How to find the kth largest element in an unsorted array of length n in O(n)?

这是使用多个迭代器的不同方法，您能帮忙比较一下其复杂性吗？

package linkedlist;

import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListTest {
    public static void main(String[] args) {
        LinkedList<String> l = new LinkedList<String>();
    l.add("11");
    l.add("2");
    l.add("3");
    l.add("14");
    l.add("5");
    l.add("16");
    l.add("7");
    l.add("18");
    l.add("9");

        int i = 1;

        Iterator<String> it = l.iterator();
        Iterator<String> it1 = l.iterator();
        Iterator<String> it2 = l.iterator();

        String mid = null;
            String third = null;

        while(it.hasNext()){
            i++;
            it.next();
            if(i%2==0){
                mid = it1.next();
            }
            if(i%3==0){
                third = it2.next();
            }
        }

        System.out.println(mid);
        System.out.println(third);
    }
}

此外，您是否可以建议使用 Java 提供的实用程序类来编写此代码的更好方法，尽量避免为 Node 等编写自定义代码？

任何帮助将不胜感激。

Answer 1

鉴于您希望按位置对其进行排序，以下是发布第 n 个元素的代码。

List<String> alist = new LinkedList<String>();
alist.add("0");
alist.add("1");
alist.add("2");

String value = alist.get(1); // returns "1"

如果你想要中间元素，我建议将列表大小除以 2 以获得索引

编辑:

尽管我认为您不希望对列表进行排序，但我认为(如果我们考虑到复杂性)，这将是最好的。

事实上，如果您使用合并排序，它应该在 O(nlog(n)) 中，然后您可以使用我为您提供的方法(我相信)在 >O(n) 因为你的数据结构没有索引。所以基本上你会在 O(nlogn)

中找到列表的第 n 个元素(假设没有重复项)

编辑2:

对于排序，我只是使用

Collections.sort(list);

根据docs :

The sort operation uses a slightly optimized merge sort algorithm that is fast and stable: