0

SO已经存在一些问题来寻找中间元素。

如何在 O(n) 中找到长度为 n 的未排序数组中的第 k 个最大元素？

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

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 等编写自定义代码？

任何帮助将不胜感激。

4

3 回答 3

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)因为您的数据结构没有被索引。所以基本上你会在你的列表中找到第 n 个元素（假设没有重复）O(nlogn)

编辑2：

对于排序，我只是使用

Collections.sort(list);

根据文档：

排序操作使用了稍微优化的归并排序算法，快速稳定：

于 2013-09-27T04:19:34.017 回答
0

我想我还是不明白这个问题。否则，这是获取列表中间索引的解决方案。如果尺寸奇数，这项工作也有效。

String mid; 
mid=l.get(((l.size())-(l.size()%2))/2);
于 2013-09-27T06:32:56.800 回答
0

如果您的列表仅包含整数，您可以使用以下解决方案。此内置排序使用 TimSort（源自合并排序）：

公共类排序列表{

public static void main(String[] args) {

    LinkedList<Integer> l = new LinkedList<Integer>();
    Collections.sort(l);
}
于 2013-09-27T10:27:16.193 回答