1

整数を含むリストがあり、最小値と最大値を見つける必要があると仮定します。それを行う最良の方法は何ですか？私は次のように考えることができます：

  1. 読み取り数が書き込み数よりもはるかに多い場合。ソートされた方法でリストを保持します。数値が追加されるたびに。並べ替えて追加します。最小値と最大値を取得するには、このリストの最初と最後の要素を取得するだけです。

  2. 書き込み数が読み取り数よりも多い場合。リストを繰り返し、結果を返します。しかし、これは高価に見える O(n) です。

他に良い方法はありますか？

4

6 に答える 6

4

リストへの変更を観察できると仮定すると、最小値と最大値を保存 (キャッシュ) し、数値が追加/削除されたときにキャッシュされた値を更新する可能性があります。この時点では、リストの順序は関係ありません。

于 2013-02-06T10:23:40.953 に答える
2

私は興味深いアイデアを提案します：

書き込みよりも読み取りが多いにもかかわらず削除が頻繁に行われると仮定すると、前の最小値と最大値（ @akaIDIOTソリューションとの違いは、これは単なる参照であるということです）。

スタック内の各値は、前の最大値と前の最小値を指します。

追加アイテムもO（1）を取り、最小値と最大値を見つけることもO（1）を取ります。

アイテムの削除はアップデートで説明されています：

欠点は、メモリ消費量が増えることです。

この解決策が間違っている場合は削除します。問題があればコメントしてください。反対票を投じる必要はありません。

アップデート

@akaIDIOTは彼のコメントの中で、私が見逃したケースについて言及しています。複数の最大値または最小値がある場合はどうなりますか。

In this case and other cases also, deleting max value will demand updating of all objects that point to it , which will be max O(n), but i think that in average it will still stay O(1). If all values are distinct this will be always O(1)

于 2013-02-06T10:35:52.767 に答える
2

そのために Collection.max() および Collection.min() 静的メソッドを使用できます...

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/Collections.html

コレクションを自動的にソートするには、SortedSet を使用します。

于 2013-02-06T10:23:35.843 に答える
1

min/max heap同様のデータ構造 (赤黒木) を使用して整数を保持することもできます。最小値/最大値の取得には時間がO(1)かかり、新しい要素の挿入にはO(log n)時間がかかります。

http://en.wikipedia.org/wiki/Min-max_heap

于 2013-02-06T10:26:54.220 に答える
0

リストからの整数の削除をサポートしていると仮定すると、どちらが高いか (読み取りまたは書き込み) に関係なく、並べ替えられたリストを使用すると作業が簡単になり、パフォーマンスが向上します。

于 2013-02-06T10:25:09.140 に答える
0

最小値と最大値を保持するカスタム リストを作成できます。これにより、O(1) 挿入、O(1) 最小値と最大値の読み取り、および O(N) 削除が得られますが、最小値または最大値を削除する場合のみです。

擬似コード:

public MinMaxList
{
    property Min; 
    property Max;

    method Add (int newValue)
    {
        if (Min is null OR newValue < Min)
            Min = newValue;

        if (Max is null OR newValue > Max)
            Max = newValue;
    }

    method Delete (int value)
    {
        if (value = Min or value = Max)
            //Rescan list to determine new Min and Max values. This is O(N).
    }

}
于 2013-02-06T10:27:16.577 に答える