この質問は本物の頭脳派向けです。なぜなら、補助配列なしで行う必要があり、最も効率的でなければならないからです!
C プログラム - X の数値 (X=4 配列: 5,4,3,2 と仮定) を含む配列を受け取り、配列に 0 から X-1 までのすべての数値があるかどうかを確認する必要があります (X が 44 の場合は確認する必要があります)。配列内のすべての数値が 0 ～ 43 の場合)。
それは非常に効率的でなければなりません - つまり、アレイ上で 43 回実行するという選択肢はありません!
これを行う方法はありますか?? 私は何時間も成功せずにこれを理解しようとしています!!
O（n）でなければなりません。
配列の順序の変更が許可されている場合は、インプレース ソート アルゴリズムを使用できます。
array[i] == array[i+1]
その場合、時間の複雑さは O(n*lg n) になります。
問題を単純化して、重複を見つけることができます。
証拠：
それがあれば、次の実装を使用できます: Finding duplicates in O(n) time and O(1) space。また、配列の境界を確認してください。数値が境界内にない場合、配列には正しくない数値が含まれます。
これにより、O(n) ソリューションが得られます。
両方の配列を並べ替えます ( にありますO(n log n))。次に、両方の配列をキューとして扱います。
O（n）ソリューション：アルゴリズムは、元の位置を占める要素と交換することにより、配列内の各要素を正しい位置に配置しようとします。たとえば、1をa [0]に、2をa[1]に配置します。
最初は、i = 1、a [i --1] = 1、それは大丈夫で、何も触れられません
i = 1
a = 1 6 3 4 5 7 1
次に、i = 2、a [i --1] = 6！= 2、次にa[i-1]とa[6-1]を交換します。
i = 2
a = 1 7 3 4 5 6 1
その場合、iはまだ2ですが、a [i --1] == 7！= 2であり、a[i-1]とa[7-1]を交換します。
i = 2
a = 1 1 3 4 5 6 7
ここでi=2ですが、a [i --1] == a [1 -1]であることがわかります。したがって、重複が見つかります。
完全なソース：
#include <stdio.h>
int main() {
int a[7] = {1, 6, 3, 4, 5, 7, 1};
int i, t;
for (i = 0; i < 7; ++i) {
while (a[i] != i + 1) {
if (a[i] == a[a[i] - 1]) {
printf("duplicate: %d\n", a[i]);
goto out;
}
t = a[i];
a[i] = a[a[i] - 1];
a[t - 1] = t;
}
}
printf("no duplicate\n");
out:
return 0;
}
ここでいくつかの素晴らしい答えを参照してください。@cafの答えのC++実装は、
bool stop=true;
//最初に要素iを場所A [i]に配置する、つまり4をA[4]に配置することができます。
for(int i = 0; i<n; i++) {
while (A[A[i]] != A[i]){
swap(A[i], A[A[i]])
}
}
// than u can have the second loop which does the decision
for(int i = 0; i<n && !stop; i++) {
if (A[i] != i){
stop = true;
}
}
if (stop)
printf("duplicate");
else
printf("not duplicate)
foreach(int i in array)
{
int count = 0;
foreach(int i2 in array)
{
if(i == i2)
{
count++;
}
}
if(count > 1)
{
return false;
}
}
return true;
配列を並べ替えてから、一度スキャンすることができます。これにより、単純なアプローチに必要な O(N^2) よりも優れた O(N log N) パフォーマンスが得られるはずです。
配列が両方ともソートされている場合は、変更されたマージ操作 (mergesort で使用されるものなど) を使用できます。
提案された解決策よりも[平均的に]うまくいくことができますO(nlogn)。
ハッシュテーブルを使用した武装化された平均的なケースのソリューション
があります。O(n)
hash <- new hash set
for each e in A:
hash.add(e)
for each e in B:
if hash.contains(e): print e
「印刷された」要素の追加のハッシュセットを保存することにより、要素が B に 2 回出現する場合に要素を 2 回印刷することを克服できます。
遅延または最悪の場合のパフォーマンスに問題がある場合は、提案されている並べ替えと反復のソリューションのいずれかを使用してください。
小さい方をソートし、二分探索を使用して大きい方の各要素を検索します。そうすれば、配列のサイズが小さいO((n1+n2)*log(n1))場所で実行できます（小さい方です）。n1, n2n1
答えについてはこれを読んでください-配列の検証-補助配列を使用せずに
0 から n-1 までの要素を含む n 要素の配列で、これらの数字のいずれかが何度でも出現します。
たとえば、n を 7、配列を {1, 2, 3, 4, 5, 4, 6} とすると、答えは FALSE になります。
上記のステートメントは矛盾していませんか?!
この質問で何が欠けているのかわかりませんが、私の知る限り、（合理的な）解決策がO(n)時間（および空間）の複雑さよりも/悪いものでなければならない理由がわかりません。
上記のコメントと回答から、次のことを理解しています。
check if all the array has all the numbers from 0 to X-1。したがって、配列内でそれ以下のもの0は想定されていません。したがって、負の数は許可されていないと思いますcheck if all the array has all the numbers from 0 to X-1。X0X-1したがって、上記の仮定を行うと、1 ビットを使用してi( 0 <= i <= X-1) が存在するかどうかを確認できます。が重複している場合i、重複した番号があることを言及するのに失敗します。
配列全体を1回スキャンし、O(n)要素ごとに1ビットを使用するだけなので、ビットXが必要です-たとえば、要素を処理する必要があり、配列要素を保持するためにメモリが必要であり、配列要素を格納するためにのみ使用される要素の存在。10X1000000sizeof(int)43.82M0.48M
#include <stdio.h>
#define X 10
#define MIN 0
#define MAX X-1
int main(void)
{
//int arr[X] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
//int arr[X] = {6, 7, 8, 9, 0, 5, 3, 2, 11, 12};
//int arr[X] = {1, 1, 2, 4, 5, 6, 7, 8, 2, 2};
int arr[X] = {1, 3, 2, 4, 5, 6, -7, 8, 2, 2};
/* if X is more than sizeof(int) then change
the flag type to a wider one! */
int flag = 0;
int i;
for(i=0 ;i<X ; i++) {
if (arr[i] >= MIN && arr[i] <= MAX) {
if (flag & 1<<arr[i]) {
printf("Duplicate found : %d \n", arr[i]);
return -1;
}
flag |= 1<<arr[i];
} else {
printf("Failure at %d : %d \n", i, arr[i]);
return -1;
}
}
printf("Success \n");
return 0;
}