1

私はこの問題の効率的な解決策を実装しようとしています。「1からnの範囲の並べ替えられていない配列で、数値が削除されたかどうか、およびn個の数値が削除された場合はどうなるか」。

私はコーディングに問題はありません。誰かが私の基本的なアイデアを提供してくれるなら、私はここにいます。すべての要素をハッシュテーブルに格納し、インデックスを数値自体（つまり、hash（1）= 1）にして、後で1からnまでハッシュテーブルに値が存在するかどうかを確認すると思いました。これにはO（n）時間がかかります。もちろん、複数の番号を削除する場合は、これを提案します。単一の値の場合、1からnまでのnumの合計を計算し、配列の合計を減算します。

ただし、削除されたn番号については、効率を上げるために追加できるものがあります。（私の解決策が（O（12）= 12 = -12）のように格納することであるにもかかわらず、負の数が含まれる場合、基本的な連鎖ですが、時間計算量は自動的にO（2nに増加します）。この問題が実際に私が質問している理由です。 、しかしそれでも唯一のポジティブのためのどんな考えも役立つかもしれません。）

4

4 に答える 4

2

あなたの解決策は最高です、あなたはO（N）よりも複雑にすることはできません（O（2N）は実際にはO（N）です）あなたがあなたの価値をマッピングする良い関数を持っているならあなたが負の数を持っていても関係ありません。数値の場合、nより小さく、素数となる数値を提案します。その数値をPと呼びましょう。f（x）= x％P（値xの場合、キーはx％Pになります）P = 9913の場合、 hash [10] = 10、9923、-9903であり、（それらの値）％Pを持つすべての数値は、配列の10と等しくなります。リンクリストまたはベクトルを使用して、衝突を取り除くことができます。数値Yの場合、YをインデックスY％Pに格納する必要があり、範囲（1..n）のiの1つの走査で、i（基本的にO（1）の位置i％Pのハッシュテーブルを調べる必要があります。 ）クエリの複雑さ）そしてそれだけです。お役に立てば幸いです。私の英語でごめんなさい:(

于 2012-06-11T19:04:32.517 に答える
0

この問題に対して複数のデータ構造を定義できると思います。たとえば、INT del=0を定義します。del_listを定義すると、del_listのノードはアドレスと番号を記録できます。ソートされていない配列Aがあります。この配列Aから番号を削除する場合は、削除した番号をdel_listとdel++に追加します。そのため、削除された番号の数とその数を知ることができます。その上、エンコードすればこの問題を解決するより効率的な方法があると思いますが、今はわかりません：P..この回答がお役に立てば幸いです。

于 2012-06-11T00:34:21.003 に答える
0

ハッシュテーブルを使用するソリューションでは、ハッシュテーブルは必要ありません。値が1からnであることがわかっている場合は、nサイズのブール値の配列を使用できます。値の配列を反復処理し、その値を使用してブール値の配列にインデックスを付け、その場所の値をTrueに設定するだけです。その後、ブール値の配列を反復処理し、False値を探して、削除された値を確認します。intの配列を使用し、ビット位置にTrue / False値を設定すると、使用するスペースを減らすことができます。これはカウントソートです

for i=0 to n:
    bools[values[i]] = True:
for i=0 to n:
    if(bools[i] == False):
        print("%d is missing".format(i))

負の値が与えられた場合は、最初に配列を通過して最小値を見つけます。-10の場合は、すべての値に10を加算して、-10が位置0に移動するようにします。次に、上記のロジックを使用し、負の値が見つかったら10を減算します。

「1からnの範囲のソートされていない配列で、数値が削除されたかどうか、およびn個の数値が削除された場合はどうなるかをどのように見つけると仮定しますか？」

n個の数値が削除された場合、配列には値が含まれません。

于 2012-06-11T01:19:00.367 に答える
0

リストをスキャンする前にある程度の前処理が許可されている場合は、予想される数の二重リンクリストを維持する前処理されたデータ構造を作成し、スキャン時にそのリンクリストから要素を削除できます。入力の数字のシーケンス。二重リンクリストに残っているものはすべて、入力から欠落しているものです。

リストのノードは実際には配列から作成されているため、二重リンクリストのメンバーへのアクセスはO（1）です。二重リンクリストからの削除はO（1）です。したがって、欠落している番号は、入力の1回のパスで検出されます。複雑さはO（i + m）で、iは入力のサイズであり、mは欠落している数値の数です。

以下のコードは、入力が比較されるシーケンスの開始値と終了値に基づいて、二重にリンクされたリストを作成します。それを使用すると、次のようになります。

Tracker t(0, 10);
int i;
while (std::cin >> i) t.remove(i);
t.report();

楽しみ！

struct Node {
    static int index;
    static int stop;
    int num;
    struct Node *next;
    struct Node *prev;
    Node () : num(index++), next(0), prev(0) {
        if (index <= stop) next = this + 1;
        if (index > 0) prev = this - 1;
    }
};

struct Tracker {
    int start;
    int finish;
    Node *nodes;
    Tracker (int s, int f) : start(s), finish(f) {
        if (finish < start) throw 0;
        Node::index = start;
        Node::stop = finish + 1;
        nodes = new Node[finish - start + 2];
        nodes[finish - start + 1].next = nodes;
        nodes[0].prev = &nodes[finish - start + 1];
    }
    ~Tracker () { delete[] nodes; }
    void remove (int i) {
        Node *n = &nodes[i - start];
        n->prev->next = n->next;
        n->next->prev = n->prev;
    }
    void report () {
        Node *n = nodes[finish - start + 1].next;
        if (n->next == n) std::cout << "all there" << std::endl;
        else do {
            std::cout << "missing: " << n->num << std::endl;
            n = n->next;
        } while (n != &nodes[finish - start + 1]);
    }
};
于 2012-06-11T04:24:13.337 に答える