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元素

回答

相关问题