配列から値を削除するだけなら・・・
配列 A から 配列 B の値を削除せよというのが問題の趣旨です。配列の長さは最大で100です。
配列ではなくリストにしてRemoveメソッドで要素を取り除いていくだけ。なんということはありません。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { List<int> ReadIntList() => Console.ReadLine().Split().Select(_ => int.Parse(_)).ToList(); List<int> vs = ReadIntList(); int N = vs[0]; int M = vs[1]; List<int> A = ReadIntList(); List<int> B = ReadIntList(); foreach (int b in B) A.Remove(b); Console.WriteLine(string.Join(" ", A)); } } |
配列のサイズが大きい場合
ただこの問題、N と M が小さな値だからこんな方法でもできたのであって、もっと大きな値だったらどうなるのでしょうか？
以下のコードは 10^5個の乱数を生成して配列 A から 配列 B の値を削除する処理をおこなっています。実行してみると時間がかかります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { List<int> A = new List<int>(); List<int> B = new List<int>(); Random r = new Random(); for (int i = 0; i < 10 * 10000; i++) { A.Add(r.Next()); B.Add(r.Next()); } Console.WriteLine("処理開始"); List<int> C = Solve(A, B); Console.WriteLine(C.Count); } static List<int> Solve(List<int> A, List<int> B) { foreach (int b in B) A.Remove(b); return A; } } |
処理速度を向上させるには B の要素の値はそれぞれ何個ずつあるのかを先に取得して辞書にしておき、辞書内にない場合だけ A の要素を 戻り値であるリスト C に追加するようにします。これだと処理は一瞬で終わります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
static List<int> Solve(List<int> A, List<int> B) { Dictionary<int, int> dic = new Dictionary<int, int>(); for (int i = 0; i < B.Count; i++) { int b = B[i]; if(!dic.ContainsKey(b)) dic.Add(b, 0); dic[b]++; } List<int> C = new List<int>(); foreach (int a in A) { if(dic.ContainsKey(a)) { dic[a]--; if (dic[a] == 0) dic.Remove(a); } else C.Add(a); } return C; } |
Linq拡張メソッドのExceptメソッド
ところでLinq拡張メソッドのExceptメソッドを使うと差集合を取得することができますが、この問題の場合は使えません。
問題文にはこうあります。
数列 A が B_i を要素として持つならば、そのような要素を 1 つ選び、削除する。
ところがExceptメソッドを使うと数列 A が B_i を要素として持つ場合、そのような要素をすべて削除してしまいます。ただExceptメソッドの動作速度は高速です。
