3

私は宿題の問題を抱えていますが、それはO(max(F)*N)(Nについて10^5であり、Fであり10^9) 複雑な場合にのみ解決できます。助けていただければ幸いです。4 つの数字Nのセット(とという名前)が与えられます。4 つの数値の各セットは、次のように数値のセットを記述します。含まれている最初の連続した数値がセットに含まれます。次の連続する数字はそうではなく、次の数字は、上限に達するまでこれを繰り返します。たとえば、セットが含まれている場合、セットが含まれていますintegerS, F, abSbaFS=5;F=50;a=1;b=19(5,25,45); S=1;F=10;a=2;b=1(1,2,4,5,7,8,10);

奇数個のセットに含まれる整数を見つける必要があります。与えられたテストでは、この条件を尊重する数値は 1 つだけであることが保証されています。

min(S)との間のすべての数字max(F)を調べてみましたが、この数字が何セット含まれているかを確認し、奇数セットに含まれている場合は、これが答えです。私が言ったように、このようにして私O (F*N)はあまりにも多くの数を取得し、数が奇数のセットにあるかどうかを確認する方法が他にありません.

あなたが私を助けることができれば、私は本当に感謝しています. 事前に感謝し、私の悪い英語と説明で申し訳ありません!

4

4 に答える 4

3

ヒント

私は二分法を使いたくなるでしょう。

値 x を選択し、すべてのセットに存在する <=x の数を数えます。

これが奇数の場合、答えは <=x、そうでない場合は >x です。

これには時間がかかります O(Nlog(F))

別の説明

セットがあるとします

[S=1,F=8,a=2,b=1]->(1,2,4,5,7,8) 
[S=1,F=7,a=1,b=0]->(1,2,3,4,5,6,7) 
[S=6,F=8,a=1,b=1]->(6,8)

次に、テーブルを作成できます。

N(y) = y がセットに含まれる回数、

C(z) = sum(N(y) for y in range(1,z)) % 2

y  N(y)  C(z)
1  2     0
2  2     0
3  1     1
4  2     1
5  2     1
6  2     1
7  2     1
8  2     1

次に、二分法を使用して、C(z) が 1 になる最初の場所を見つけます。

于 2012-05-09T18:31:35.120 に答える
1

実際のセットを生成することなく、これらのセットに対してセット操作、特に交差を実行する方法を見つけることが役立つようです。それができれば、テストでこれらすべてのセットを交差させると、1つの数字だけが残るはずです。aと部分を除いbて、SとFの間のすべての整数を含む2つのセットの共通部分をどのように取るかを簡単に確認できます。共通部分はS = max（S1、S2）とF = min（F1）のセットです。 、F2）。

それはあなたに出発点を与えます。ここで、2つのセットの共通部分を作成する方法を理解する必要がaありbます。

于 2012-05-09T18:18:06.003 に答える
1

救助へのXOR。

連続する各セットから数値を取得し、それらを結果セットの内容と XOR します。つまり、番号が現在「存在する」とマークされている場合は、それを「存在しない」に変更し、その逆も同様です。

最後に、結果セットに存在としてマークされた数字が 1 つ表示されます。これは奇数回発生した数字です。他のすべては偶数回 XOR されるため、元の状態に戻ります。

複雑さに関しては、各入力項目を 1 回だけ処理するため、基本的には入力項目の総数に比例します。少なくとも、結果セットに対する操作が一定の複雑さであると仮定します。少なくとも、彼らがどのように表現しているのかを理解すれば、それは要件を満たしているようです.

于 2012-05-10T02:26:02.420 に答える
0

S は非負であると想定されているようです。O(max(F)*N)時間境界が必要な場合は、ふるい分けのようなアプローチを使用できます。

各候補番号 (つまり、min(S) と max(F) の間のすべての番号) のエントリを持つ整数の配列があります。すべての 4 倍体を通過し、各 4 倍体によって表される含まれる数値に関連付けられているすべての配列位置に 1 を追加します。最後に、配列を調べて、どのカウントが奇数かを確認します。それが表す数は、あなたの条件を満たす数です。

これが機能するのは、N 個の 4 倍を下回っており、含まれる数をカウントするのにそれぞれ O(max(F)) 以下の時間 (S が常に非負であると仮定) しかかからないためです。これにより、O(max(F)*N) が得られます。

于 2012-05-09T18:41:10.900 に答える