どこかの掲示板で見掛けたネタ。
「配列やコレクションから重複要素を取り除きたい」
ふむ。たとえば { 1, 3, 5, 1, 5, 2, 4 } → { 1, 3, 5, 2, 4 } ってことやね。
与えられた集合をソートしてかまわんなら話は簡単。
一旦ソートし "いっこ前のと同じでなければ列挙" すればいい。
ソートしちゃいけないとなると、"これさっき出てきたっけ?" を憶えておくナニカが要るでしょう。
using System;
using System.Collections.Generic;
class Program {
public static IEnumerable<T> Unique<T>(IEnumerable<T> en) {
List<T> mark = new List<T>();
foreach ( T item in en ) {
if ( !mark.Contains(item) ) { // 既出でないなら
mark.Add(item); // 追加して
yield return item; // 返す
}
}
}
public static void Main() {
int[] array = { 1, 3, 5, 1, 5, 2, 4 };
foreach ( int item in Unique<int>(array) ) {
Console.Write("{0} ", item);
}
}
}
んー、要素数が多くなければこれでもいいんだけど、大量の要素となると遅くなります。
using System;
using System.Collections.Generic;
class Program {
public delegate
Result BinaryFunction<Arg1,Arg2,Result>(Arg1 arg1, Arg2 arg2);
// BinaryFunction → IComparer に変換
private class cmp<T> : IComparer<T> {
private BinaryFunction<T,T,bool> pred;
public cmp(BinaryFunction<T,T,bool> p) { pred = p; }
public int Compare(T x, T y) {
return pred(x,y) ? 1 : (pred(y,x) ? -1 : 0);
}
}
public static IEnumerable<T>
Unique<T>(IEnumerable<T> enumerableT, BinaryFunction<T,T,bool> comp) {
SortedDictionary<T,object> dic
= new SortedDictionary<T,object>(new cmp<T>(comp));
foreach ( T item in enumerableT ) {
if ( !dic.ContainsKey(item) ) { // 既出でなければ
dic.Add(item,null); // 追加して
yield return item; // 列挙
}
}
}
public static void Main() {
int[] array = { 1, 3, 5, 1, 5, 2, 4 };
foreach ( int item in
Unique<int>(array, delegate(int x, int y) { return x < y; }) ) {
Console.Write("{0} ", item);
}
}
}
これでどうだろ。時間計算量はO(logN)