4

我有一个相当独特的要求，在我的集合中应该只包含 Top 和 Bottom n 元素。这些元素是可比较的，并且集合本身是有界的，这意味着评估是在向集合添加条目时完成的。

例如，当以下一组值插入到“Top and Bottom 10”集合中时

5、15、10、1、12、8、11、2、16、14、9、3、20、7

该集合应仅包含以下内容

20、16、15、14、12、7、5、3、2、1

我正在考虑维护 2 个由 n/2 个元素组成的 SortedSet，然后最后将它们合并，但是这种方法并不干净，需要在使用结果之前进行合并步骤。

只是希望有人会对这个问题有更好的答案。

4

2 回答 2

1

1.你想要排序和唯一性，使用TreeSet from java.util.Collection。您的数据将按自然顺序自动排序并保持唯一性。

2.Collections.reverse()根据需要使用反转集合...

于 2012-07-24T18:47:41.560 回答
0

因为我喜欢在这样的周日下午写文集，

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)检查是否为负，然后返回表单的表达式以获取插入点或前后点。nm-1-n

于 2012-11-26T00:26:31.323 回答