Ｃ言語・要素除去

配列を用意して、それぞれ実体として、さまざまな値を入れたとしたとき、

その配列の、ある要素と、別の要素に重複した値があったとします。

ここで、
重複した値を取り除いて、取り除いた分、そのあと、要素番号を詰める。

という作業をしたいのですが、どのような手順がありますでしょうか。


考え方を知りたいので、できれば、ソースより言葉で教えていただけるようお願いします。

No.2 ベストアンサー 回答者： yama1718 回答日時： 2011/08/04 01:39

私はソートを利用した方法を提案します。

これなら配列の数が非常に多くても効率よく処理できると思います。

1.配列は値とポインタと削除フラグの３つを対にした構造体の配列にする
2.同じ配列をもう一つ作成して内容をコピーする
3.コピーした配列のポインタは元の配列へアクセスできるようにセットする
4.コピーした配列をソートする（ペアのポインタも一緒にしてソートする）
5.ソートした配列のポインタから元の配列へアクセスして相互にアクセスできるようにポインタをセットする

つまり、同じ配列を用意して片方はソートで並び替えて、互いに対のポインタを通して配列の値を読み取れるようにします。
この下準備ができれば、次の手順で同じ番号を詰める事ができます。

1.削除フラグには配列の番号を入れておく
2.配列を最初から読み取って、ソートした方の配列の前後の値を読み取る
3.もしソートした方の配列の前後の値がどちらも違えば、その配列の値は一つだけなので、そのまま次へ
4.ソートした配列で前の値が違って、後の値が同じなら、それは最初に出てきた値なので、そのまま次へ
5.上記の２つの条件で、それ以外だったなら二回目以降の重複する値なので、削除フラグを立てる（99999など大きい値にする）
6.配列を最後まで読み取ったら、削除フラグでソートすると重複した値だけ後ろの方に移動します。
順番に詰めるよりもソートを利用する方がかなり高速になります。

ここで注意するのはソートのアルゴリズムでクイックソートだと同じ値の順番が元の順番と違う場合があるので（安定ソートでない）比較する値を操作して安定ソートにさせるか、他の安定なソートのアルゴリズムを使う必要があります。

No.5 回答者： Tacosan 回答日時： 2011/08/04 14:28

#2 のように「ソートして隣接要素間でチェック」が簡単かつアルゴリズム的には最速.

C++ なら配列 a に対して
#include <algorithm>
stable_sort(a, a + sizeof a/sizeof a[0]);
int *last = unique(a, a + sizeof a/sizeof a[0]);

No.4 回答者： akayoroshi 回答日時： 2011/08/04 13:08

言葉で説明するのは、ソースを書くより面倒なので、ソースコードを載せます。

int elimination( int x[], int n, const int MARK ) {
// 値が MARK とは異なる要素だけを残す。
// 戻り値は、重複していない要素の数である。
int m=0;
for ( int i=0; i<n; i++ ) {
if ( x[i]!=MARK ) x[m++]=x[i];
}
return m;
}

void dupcheck( int x[], int n, const int MARK ) {
// 最後の要素から最初の要素に向かって順番に、
// それよりも前に同じ値の要素があれば、値を MARK に置き換える。
for ( int i=n-1; i>0; i-- ) {
int j=i-1;
while ((j>=0)&&(x[i]!=x[j])) j--;
if ( j>=0 ) x[i]=MARK;
}
}

int eliminateduplication( int x[], int n ) {
// MARK は、データがとり得ない値にしておく。
// 戻り値は、重複を詰めた後の要素の数である。
int MARK=-2147483648; // INT_MIN
dupcheck( x, n, MARK );
return elimination( x, n, MARK );
}
// 使用例
#include <iostream>
int main() {
int x[]={ 4,3,1,4,2,8,1,7,8,5,5 };
int n=sizeof x / sizeof( int );
int m=eliminateduplication( x, n );
for ( int i=0; i<m; i++ ) std::cout << x[i] << " ";
std::cout << std::endl;
}

データの数が100個程度以下でしたら、ソートするよりも効率は良いと思います。

No.3 回答者： saijyo_739 回答日時： 2011/08/04 09:25

ソースも言葉も同じかとも思いますが。

最初から見ていき、確定している(重複しない)要素を増やしていけば良いかと。
最初に重複している要素が見つかって以降は重複しない要素が見つかれば確定している最後の要素番号へコピーすれば良いかと。


#include <stdio.h>

int main( void )
{
int sample[] = { 3, 5, 8, 2, 8, 1, 5, 9, 11 };
int uli; /* uniq last index */
int chi; /* checked index */
int lai; /* last index */
int isUniq;
int work;

for( uli=chi=1, lai=sizeof(sample)/sizeof(int); lai>chi; chi ++ ) {
for( isUniq=1, work=0; uli>work; work++ ) {
if( sample[work] != sample[chi] ) continue;
isUniq=0;
break;
}
if( isUniq ) {
if( chi != uli ) sample[uli] = sample[chi];
++ uli;
}
}
for( work=0; uli>work; work ++ ) printf( "No.%d %d\n", work+1, sample[work] );

return 0;
}

No.1 回答者： asuncion 回答日時： 2011/08/03 22:04

a[0]=1

a[1]=2
a[2]=3
a[3]=2
a[4]=4
a[5]=5

とすると、a[1]とa[3]が同じ値（2）ですね。そうすると、重複値を取り除いて詰めた結果は

a[0]=1
a[1]=2
a[2]=3
a[3]=4
a[4]=5

になりますね。このとき、a[5]をどうするかは、プログラムの仕様によると思います。

さて、重複値を見つけることと、それを取り除いて後ろから前に詰める操作を
手で行なうとき、どういう風にしますか？
手で行なうプロセスをそのままソースコードに落とし込めば、完成です。