重複する要素を取り除く in C DouKaku?

与えられたリストxsの中から、 2回以上出現するものを全部取り除いてください。

サンプル入力
[3, 1, 4, 1, 5, 9, 2, 6, 5]
サンプル出力
[3, 4, 9, 2, 6]

これはアレイのuniqの派生問題です。リストとかアレイという言葉は言語によってまちまちの意味で使われているので、「配列のようなもの」という漠然とした意味にとって構いません。

引数の配列を書き換えて。

#include <stdio.h>

int only_uniq(int *a, int len) {
	int i, j, dup = -1;
	int n, skip;
	
	for (i = 0; i < len; i++) {
		for (j = i + 1; j < len; j++) {
			if (a[i] == a[j]) {	
				dup = i;
				i = len;
				break;
			}
		}
	}
	
	if (dup == -1) return len;
	skip = a[dup];
	
	for (i = dup + 1; i < len; i++) {
		if ((n = a[i]) == skip) continue;
		for (j = i + 1; j < len; j++) {
			if (a[j] == n) {
				a[i] = skip;
				a[j] = skip;
			}
		}
	}
	
	j = 0;
	for (i = 0; i < len; i++) {
		if (a[i] != skip) a[j++] = a[i];
	}

	return j;
}

int main() {
	int a[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5 };
	int i, len;
	
	len = only_uniq(a, sizeof(a) / sizeof(a[0]));
	
	for (i = 0; i < len - 1; i++) {
		printf("%d, ", a[i]);
	}
	if (len > 0) printf("%d\n", a[i]);
	
	return 0;
}

Cで。ちょっとひねくれてみました。

入力は非負整数限定で、取り得る最大の要素がわかっているとします(コード中ではMAXVAL)。
わからなければ一回スキャンして最大値を探せば良いだけですが。

配列linkは入力値が取り得る各要素に対応し、「要素が出現する順番に並べた時に、次に出現する要素」が格納されます。ポインタを使わない一種のリンクトリストです。表示部ではそのリンクをたどりながら、重複が無かった要素を出力します。

#include <stdio.h>
#define MAXVAL 10

static int input[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5 };

int main(void)
{
    int dup[MAXVAL+1], link[MAXVAL+1], i, j;
    int len = sizeof(input)/sizeof(int);
    for (j=0; j<MAXVAL+1; j++) dup[j] = link[j] = -1;
    for (i=0,j=MAXVAL; i<len; i++) if (!++dup[input[i]]) j = link[j] = input[i];

    for (j=link[MAXVAL]; j>=0; j=link[j]) if (!dup[j]) printf("%d ", j);
    printf("\n");
    return 0;
}

DouKaku?

重複する要素を取り除く

Posted feedbacks - C

Index

Feed

Other

Link

Pathtraq