有沒有一種數據結構能夠獲得N個最偉大的元素的集合，用Java實現？

java中有TreeSet數據結構，它提供了獲取1個最大元素的能力。我需要能夠獲得N個最偉大元素集合的數據結構。有沒有一種數據結構能夠獲得N個最偉大的元素的集合，用Java實現？

我需要水木清華這樣的：

GreatestN<Integer> greatest = new GreatestN<>(Arrays.asList(5, 2, 1, 7)); 
greatest.getN(2); // returns {1, 2} 
greatest.getN(3); // returns {1, 2, 5} 

greatest.add(0); 
greatest.getN(2); // returns {0, 1}

來源

2017-02-17 Wsl_F

您可以排序的數據結構，從它那裏得到一個'Iterator'，然後得到無論你需要多少元素。只記得按降序排序。 – Kevin

當然我可以:)但如果數據結構（我問）存在，我認爲使用它會更好。 –

您可以從'TreeSet'獲得遞減迭代器。 – shmosel

感謝所有的答案和意見，特別是shmosel的那些：

你可以從TreeSet遞減的迭代器。

它看起來像結構我問不存在，但它可能是簡單的創建：

public class TreeSetMy<E> extends TreeSet<E> { 

    public ArrayList<E> getFirstN(int n) { 
     if (n > this.size()) { 
      n = this.size(); 
     } 

     ArrayList<E> firstN = new ArrayList<>(n); 
     Iterator iter = this.iterator(); 

     for (int i = 0; i < n; i++) { 
      firstN.add((E) iter.next()); 
     } 

     return firstN; 
    } 
}

來源

2017-02-17 18:22:21

您可以按照您的列表，然後通過索引值，以獲得最大的作用。

List<Integer> greatest = Arrays.asList(5, 2, 1, 7); 
    Collections.sort(greatest); // By default sorts ascending 
    System.out.println(greatest.get(greatest.size()-1)); //will give you greatest element in the list. 
    //System.out.println(greatest.get(greatest.size()-1-nthNumber)); 
    System.out.println(greatest.get(0));//will give you lowest element in the list.

來源

2017-02-17 16:57:34 Maverick

謝謝，但是你的解決方案需要很大的時間複雜度。它在每次獲得請求之前對整個列表進行排序。所以複雜性是'O（m * log（m）），其中m = list.size（）'。 –

TreeSet有方法來獲取基於元素（headSet和tailSet）的值的子集，但不被索引。對於基於索引的方法，您需要使用List和subList()。

List<Integer> list = Arrays.asList(5, 2, 1, 7); 
list.sort(); 
List<Integer> topFive = list.subList(0, 5);

來源

2017-02-17 17:01:53 Kayaman

我找不到解決方案，您的問題在線已經可用，所以我寫了一個。

如果您只想使用您提供的代碼而不修改它，請將我的代碼添加爲項目中的類。

public class GreatestN <T extends Comparable<T>>{ 


    private List<T> list; 

    public GreatestN(List newList){ 

     this.list = newList; 

     Collections.sort(list); 

    } 

    public List getN(int numbers){ 

     List<T> returnList = new ArrayList(); 

     if(numbers>list.size()){ 
      numbers = list.size(); 
     } 

     for(int i = 0; i < numbers; i++){ 

      returnList.add(this.list.get(i)); 

     } 

     return returnList; 
    } 

    public void add(T t){ 

     list.add(0,t); 

     Collections.sort(list); 

    } 

}

來源

2017-02-17 17:36:35 Tacolibre

有沒有一種數據結構能夠獲得N個最偉大的元素的集合，用Java實現？

回答

相關問題