相关疑难解决方法(0)

我是Java的初学者.请建议可以/应该使用哪些集合来维护Java中的排序列表.我曾尝试Map和Set,但他们不是我所期待的.

我正在寻找java.util包中的数据结构.我需要它来满足以下要求:

• 元素的数量(理论上)是无界的.
• 元素按升序排序.
• 你可以获得第n个元素(快速).
• 您可以删除第n个元素(快速).

我希望找到一个可索引的跳过列表,但我没有.他们是否有任何符合我所述要求的数据结构？

ListJava中是否存在基于提供的维护顺​​序的现有实现Comparator？

可以通过以下方式使用的东西:

Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);

使得someT被插入,使得在列表中的顺序是根据保持cmp

(关于@andersoj的建议我正在完成我的问题,还有一个请求)

此外,我希望能够按排序顺序遍历列表而不删除元素,即:

T min = Const.SMALLEST_T;
for (T e: l) {
  assertTrue(cmp.compare(min, e) >= 0);
  min = e;
}

应该通过.

欢迎所有的建议(除了告诉我Collections.sort在无序的完整列表中使用),但是,我更喜欢某些内容java.*或最终,org.apache.*因为此时很难引入新的库.

注意:(UPDATE4)我意识到这种列表的实现性能不足.有两种一般方法:

1. 使用链接结构(种类)B树或类似物
2. 使用数组和插入(使用二进制搜索)

没有1. CPU缓存未命中问题No 2.在数组中移位元素有问题.

UPDATE2: TreeSet不起作用,因为它使用提供的比较器(MyComparator)来检查是否相等,并基于它假设元素相等并排除它们.我需要那个比较器只用于排序,而不是"唯一性"过滤(因为元素按其自然顺序不相等)

UPDATE3: PriorityQueue不能正常工作List(因为我需要),因为没有办法按照"排序"的顺序遍历它,要按排序顺序获取元素,你必须从集合中删除它们.

更新:

类似的问题:
Java中Java 排序数组列表的良好排序列表

我有一个随机数生成器,它生成之间的数字1 to k.我也有int类型(ie int[])的数组,其大小是N,其中k小于N.

现在问题是我需要将唯一生成的数字保存到数组中(拒绝生成的重复数字)并且必须维护生成的数字的顺序,而不使用任何额外的空间和O(N)复杂性.即我同一个数组我也需要保持生成数的顺序.这样我就可以按生成的顺序检索它们.假设没有使用位图或额外数组等.

它不是一个功课.这是一个面试问题.我不应该使用任何额外的空间.他让我使用k小于的事实,N你需要在同一个数组中灌输hashmap的行为.我提出了许多使用额外空格的算法,但他也拒绝使用排序,但我无法维持生成的顺序.

我正在努力学习泛型类和实现.

我正在尝试创建一个扩展ArrayList的泛型类(我知道这是不好的做法,这只是我必须要做的事情).我想使用类似的方法对arrayList中的条目进行排序(我不允许使用.sort().这是扩展类:

import java.util.ArrayList;
import java.util.*;

/**
 * extending to ArrayList
 */
public class SortedArrayList<E> extends ArrayList<E> 
{

/**
 * Constructing the super
 */
public SortedArrayList()    
{
   super();

  }

  public  void insertAndSort (E element){
  if (isEmpty()){
      add(element);
    }

  for ( int i = 0; i < size(); i++){
      E otherElement = get(i);
      if(element.compareTo(otherElement) > 0){
          add(i, element);
        }
      if(element.compareTo(otherElement) < 0) {
          add(i+1, element);
        }
    }

}

}

我想实现的类进行排序对象的compareTo方法,但是当我尝试编译SortedArrayList类它返回一个错误说"无法识别的符号 - 方法的compareTo(E)".我知道那是因为"元素"实际上不是一个要调用的对象,它意味着是通用的.有没有办法告诉编译器compareTo()方法是从一个现在不存在的对象调用的,但是它会被调用吗？