配列の中に複数存在する数がいくつあるか

お世話になります。配列の中に同じ数が存在する数がいくつあるかを調べたいのですが、途中でつまづいてしまいました。

例えば配列arrayの中に、0, 0, 5, 0, 5, 1, 5といった数が格納されているとしたら
複数ある数は０と５の２つなので、２を返す、というだけのプログラムです。

int n=array.length;
int cnt=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(array[i]==array[j]){
cnt++;
break;
}
}
}
return cnt;

forループで配列0から同じ数を順番に調べ、もしヒットすればカウントを増やして内側のループをブレイクし、配列１からまた順番に調べようとしたのですが、
上の例の場合、配列0と配列１が同じ数（0）ですので、カウントが余計に増えてしまいます。
どのように組めばうまく動作するでしょうか。宜しくお願いします。

No.4 ベストアンサー 回答者： kmee 回答日時： 2010/02/14 15:55

>ソートしたあとでも同じ数が連続してしまうので、どのようにしてカウントすればいいのでしょうか・・・

int cnt = 0;
int t = 0; //現在調べている数値が最初に出てくる位置
for( int i = 1 ; i < n ; i ++ ) {
if( array[t] != array[i] ) {
//今までと違う数値になった
if ( i > t +1) {
//次の数値の先頭(i)のが、現在の数値の先頭の隣(t+1)より大きかったら
//現在の数値は2つ以上あったということ
cnt ++ ;
}
//次からは、iの位置を先頭として調べる
t = i;
}
}

//配列の最後に重複があっても(array[t] != array[i])で判定ができないので
//ループの外で判定する
if ( n > t + 1) {
cnt ++ ;
}

この回答へのお礼

大変参考になりました！本当にありがとうございました！

お礼日時：2010/02/15 13:00

No.3 回答者： kmee 回答日時： 2010/02/13 14:51

アイディア1)

集計済を示すboolean配列(長さはarrayと同じ)を作って(checkedとでもしておく)、falseで初期化しておく。
重複していたら、 checkedの対応する要素をtrueにする。
checkedがtrueならすでに確認済なので次へ。

int n=array.length;
int cnt=0;
boolean[] checked = new boolean[n] ;
java.util.Arrays.fill(checked,false);

for(int i=0;i<n;i++){
//array[i]がすでに重複として判定済なら次へ
if ( checked[i] ) {continue ;}
//重複があったことを示すフラグ
boolean isdup = false ;
for(int j=i+1;j<n;j++){
//array[j]がすでに重複として判定済なら次へ
if ( checked[j] ) {continue ;}
if ( array[i]==array[j]) ){
//全部の重複要素をchecked=trueにするためにbreakしない
checked[j]= true ;
//breakしない代りに、重複があったことを示すフラグを立てる
isdup= true ;
}
}
if ( isdup ) {
checked[i] = true ;
//重複があったらcntをインクリメント
cnt++;
}
}
return cnt;
}

アイディア2)
重複したものは配列から削除→残っている配列について重複確認
元の配列を保存するため、あらかじめコピーを作っておく必要がある

アイディア3)
arrayをソート。同じ値が並ぶので順番に数を数える
元の配列を保存するため、あらかじめコピーを作っておく必要がある

この回答への補足

みなさん　ありがとうございます！ソートで調べる方法を試してみようと思い、まずソートを作りました。

int[] a = { 0, 0, 5, 0, 5, 1, 5 };
int n = a.length;
int temp = 0;

for (int i = 0; i < n; i++) {
for (int j = 0; j < n - 1; j++) {
if (a[j] > a[j + 1]) {
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}

ここで質問なのですが、ソートしたあとでも同じ数が連続してしまうので、どのようにしてカウントすればいいのでしょうか・・・

補足日時：2010/02/13 22:42

No.2 回答者： Lchan0211 回答日時： 2010/02/13 14:41

(案1)

チェックする配列と同じ要素数を持つboolean配列を用意し、
対象配列番号が重複検出済みかどうかを表すフラグとして使う。
重複数値(array[i]==array[j])を見つけたら、
その配列番号の重複検出済みフラグをONにする。
(jのループはbreakしないで、他の同じ数値も重複検出済みに
する必要がある。cnt++はjのループ後にする。)
各配列の数値をチェックする前に、重複検出済みフラグが
ONか確認し、ONだったら、チェックをスキップする。

(案2)
チェックする配列の半分の要素数を持つint配列を用意し、
「重複数値格納配列」として使用する。
同じ数値(array[i]==array[j])を見つけたら、
「重複数値格納配列」にその数値を格納し、
格納位置の配列番号をカウントアップする。
各配列の数値をチェックする前に、「重複数値格納配列」
の中にこれからチェックする数値が存在するか
確認し、存在していたらチェックをスキップする。
「重複数値格納配列」の最終格納位置が、重複数値
検出数になる。

(案3)
配列を一旦小さい順にソートしてからチェックする。
ソートアルゴリズムは有名なものを参考に。
その後のチェックの仕方はわかると思います。

どれが一番効率いいんでしょうね・・

No.1 回答者： Tacosan 回答日時： 2010/02/13 14:40

配列を変更していいならソートしてしまえばいい. その方が悩みどころが減る.

変更しちゃだめといわれると, かえって時間がかかるんだよな～.