配列の確認

質問

【環境】Windows XP、C++

サイズがＸの配列があります。
配列は０～Ｘ－１の数値が１つずつ入れる目的で作っています。

その配列に値の重複が無く、全ての数値が入っているかを確認する処理なのですが、
自分が考えた方法で問題ないのかを確認してもらえないでしょうか？

処理としては、unsigned long long int型をフラグとして使って、（Ｘが64以上になる予定は今のところないので・・・、けど64に制限されるのが・・・。）
０が入っていたら１ビット目を立てて、１が入っていたら２ビット目を立てて、（以降最後まで続ける）にしようと思っています。
最終的に立っているフラグの数値が、２の（Ｘ＋１）乗―１とイコールかを判定。　（←計算間違ってるかも）
これで問題ないでしょうか？
他にいい案があれば教えてもらえないでしょうか？

以上、よろしくお願いします。

回答No.6

redfox63 · ベストアンサー

for (int i = 0; i < X; ++i)
　　exist[i] = 1;
を
for (int i = 0; i < X; ++i)
　　exist[a[i]] = 1;
とするだけなのでは ・・・

お礼

あ、ほんとだ。
確かにいけそうな感じに見える。
気づかなかったですよ。
ありがとうございます。

回答No.5

Tacosan

exist に入っている値は 0 と 1 しかないので「総和でこける」ことはありえません.
あ, 「0 で初期化」は必要だったっけな....

お礼

再度ありがとうございます。
この手順は、配列の値を全く使っていない気がしていたので、
どこかを記入ミスしているものだと思っていたのですが。

確かにこの手順だと総和でこける事はないのですが、
配列の内容を使っていないので、結果が変わらなく思えるのです。
どこか勘違いしているのでしたらすみません。

回答No.4

chie65536

ANo.3ですが、運悪く幾つかの条件が重なるとチェックをすり抜ける場合がある事が判明。

例えば「６が２つあって１６が無く、かつ、７が２つあって１７が無い」と言うパターンの時。確率はかなり低いが、無いとは言えない。

お礼

おっと、今処理内容を理解しようと見ていたとこだったのですが、そうなのですか・・・。
追記ありがとうです。

回答No.3

chie65536

// int array[0]～array[n]に、0～nまでの数値が重複せずに入っているか調べる
// nはX-1とする
// ＯＫならtrue、ＮＧならfalseを返す
int check(int n)
{
　　int flg = 0,i;
　　for (i = 0;i <= n;i++) {
　　　　flg ^= i ^ array[i];
　　}
　　return !flg;
}

たぶん、std::vector<int>やビットでのフラグ立てより高速。

一番の長所は「コンパイラを選ばない」って事。Ｃ＋＋はもちろん、Ｃでも動く。

回答No.2

kenmary_08

サイズがＸのchar 型の配列a[X]を作り、
　前領域を０で初期化し、
　対象の配列を読んでいき、nが入っていたら、
0<= n <Xであることを確認し、a[n-1]が０でなければ
重複あり、０ならa[n-1]=1とする。
　重複なしで、最後まで続けられたらOK

　でどうでしょうか。

お礼

確かにchar型配列でも問題ないわけですよね。
ありがとうございます。

回答No.1

Tacosan

「サイズ X の配列 a に 0 から X-1 までの数値を 1つずつ入れる」だけなら
for (int i = 0; i < X; ++i)
a[i] = i;
でいいんだけど, それは望んでいないんですよね.
X < 64 であればそれで動くはずです.
一般には std::vector<int> を使って
std::vector<int> exist(X);
for (int i = 0; i < X; ++i)
exist[i] = 1;
if (std::accumulate(exist.begin(), exist.end(), 0) == X) {
// 全部そろっている
} else {
// 足りないやつがいる
}
という感じかな?

お礼

回答有難うございます。
まず補足ですが、配列に格納されるデータはユーザが手入力（もしくは入るから読込）するものです。
ですので、入れ間違いが無いかなどを確認するための処理です。

std::accumulateについて知らなかったため、調べてみた結果、
引数の3番目が0だと総和を求める処理になるものみたいですね。

総和だと、3と5で8になる場合や、4と4で8になる場合があるので、
数字が1つずつあるのかわからないと思うのですが、
何か間違っているのでしょうか？

よろしくお願いします。