4

コレクションに Top および Bottom n 要素のみを保持する必要があるというかなりユニークな要件があります。要素は比較可能であり、コレクション自体は制限されています。これは、コレクションにエントリを追加するときに評価が行われることを意味します。

たとえば、次の値のセットが「Top and Bottom 10」コレクションに挿入された場合

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

Collection は次のもののみを保持する必要があります

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

n/2 要素の 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 に答える