已经有一些问题来寻找中间元素。
如何在 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等编写自定义代码?
任何帮助将不胜感激。
鉴于您希望按位置使用它,这是发布第 n 个元素的代码。
List<String> alist = new LinkedList<String>();
alist.add("0");
alist.add("1");
alist.add("2");
String value = alist.get(1); // returns "1"
如果你想要 mid 元素,我建议将列表的大小除以 2 以获得索引
编辑:
尽管我认为您不希望对列表进行排序,但我认为(如果我们考虑复杂性),这将是最好的。
事实上,如果你使用合并排序,它应该是O(nlog(n))
,然后你可以使用我提供给你的方法,这是(我相信)在O(n)
,因为你的数据结构没有索引。所以基本上你会在O(nlogn)
中找到列表中的第 n 个元素(假设没有重复项)
编辑2:
对于排序,我只会使用
Collections.sort(list);
根据文档:
排序操作使用略微优化的合并排序算法 快速稳定:
我想我仍然不明白这个问题。否则,这是获取列表中间索引的解决方案。如果大小是奇数,这也有效。
String mid;
mid=l.get(((l.size())-(l.size()%2))/2);
如果您的列表仅包含整数,则可以使用以下解决方案。这个内置排序使用TimSort(从合并排序派生):
公共类排序列表 {
public static void main(String[] args) {
LinkedList<Integer> l = new LinkedList<Integer>();
Collections.sort(l);
}