Java集合 - 頂部和底部n元素

我有一個相當獨特的要求，在我的集合中只應該包含頂部和底部n個元素。元素是可比較的，集合本身是有界的，這意味着評估是在向集合添加條目時完成的。Java集合 - 頂部和底部n元素

例如，當下面的值的組被插入到一個「頂部和底部10」集合

5，15％，10個，12個，8個，11個，2個，16個，14個，9個， 3，20，7

收集應僅握住以下

20，16，15，14，12，7,5，3，2，1

我想維持2的SortedSet的的n/2個元素，然後合併它們，但是這種方法並不乾淨，並且需要consumi之前的合併步驟結果。

只希望有人會有這個問題的更好的答案。

來源

2012-07-24 Anand Nadar

您可能只需要一個Treeset - 子集方法可以讓您輕鬆訪問頂部/底部5以及測試包含的較低/較高方法。 + pollFirst/Last刪除正確的項目。但是你仍然需要編碼。 – assylias 2012-07-24 18:47:35

我確實經歷了TreeSet API（子集和尾部集合），但由於大多數操作都是基於元素，而不是索引，所以我無法弄清楚如何實現。 – 2012-07-24 19:06:44

TreeSet是排序的，所以如果大小爲10，您知道子集（0,4）是前5，子集（5,9）是5（或反之亦然，我不確定） – assylias 2012-07-24 19:12:28

你想排序和唯一性，使用TreeSet from java.util.Collection。 您的數據將自動按照自然排序順序排列，唯一性保持。

2.使用Collections.reverse()到扭轉收集你的願望 ...

來源

2012-07-24 18:47:41

我確實有一個TreeSet，並且這些元素是根據我自己的比較實現進行排序的，但是此集合需要綁定到n個元素並且不超過其必需的元素。主要是爲了優化內存，因爲插入的元素數量很多。 – 2012-07-24 18:57:03

在插入數據時用一個邏輯處理它。like if（mtree.size（）> n）{//已經達到極限} else {mtree.add（value）} – 2012-07-24 18:59:25

通過這個I我能夠實現「Top N」或「Bottom N」，但不適用於「Top N和Bottom N」場景。 – 2012-07-24 19:10:08

因爲我喜歡在星期天的下午這樣寫的集合，

import static org.junit.Assert.assertEquals; 
import java.util.Arrays; 
import org.junit.Test; 

public class TopBottom { 

    public int[] top; 
    public int[] bottom; 

    public TopBottom(int size) { 
     top = new int[size]; 
     Arrays.fill(top, Integer.MIN_VALUE); 
     bottom = new int[size]; 
     Arrays.fill(bottom, Integer.MAX_VALUE); 
    } 

    public void add(int element) { 
     int n = Arrays.binarySearch(top, element); 
     if (n < -1) { 
      System.arraycopy(top, 1, top, 0, -2 - n); 
      top[-2 - n] = element; 
     } 
     int m = Arrays.binarySearch(bottom, element); 
     if (m < 0 && bottom.length >= -m) { 
      System.arraycopy(bottom, -1 - m, bottom, 0 - m, bottom.length + m); 
      bottom[-1 - m] = element; 
     } 
    } 

    public void add(int... elements) { 
     for (int each: elements) { 
      add(each); 
     } 
    } 

    public String toString() { 
     StringBuilder buf = new StringBuilder(); 
     buf.append('['); 
     for (int each: bottom) { 
      buf.append(each); 
      buf.append(", "); 
     } 
     for (int each: top) { 
      buf.append(each); 
      buf.append(", "); 
     } 
     buf.setLength(buf.length() - 2); 
     buf.append("]"); 
     return buf.toString(); 
    } 

    public static class Examples { 

     @Test 
     public void shouldHoldOnlyTopFiveAndBottomFive() { 
      TopBottom tp = new TopBottom(5); 
      tp.add(5, 15, 10, 1, 12, 8, 11, 2, 16, 14, 9, 3, 20, 7); 
      assertEquals("[1, 2, 3, 5, 7, 12, 14, 15, 16, 20]", tp.toString()); 
     } 

    } 

}

它使用Arrays#binarySearch方法，除了查找現有元素外，該元素還會將插入點返回到排序列表中（如果元素缺失）。插入點返回爲(-1-index)，因此檢查n分別是m是否定的，後面的表達式爲-1-n以獲得插入點或前後的點。

來源

2012-11-26 00:26:31 akuhn

我解決了這個問題，不能告訴哪個解決方案會更快。我的實施;對於每個插入將TreeSet元素轉換爲數組;然後查找位置（n/2）處的元素並將其從TreeSet中移除。基本上從Treeset中刪除中間元素。性能應該沒問題，因爲我們正在處理樹中有限的（n）個元素。 – 2013-04-15 19:14:42

Java集合 - 頂部和底部n元素

回答

相關問題