2015年02月11日

C#で仲間はずれの判定

   このエントリーをはてなブックマークに追加 Clip to Evernote
どう書く?orgに感謝を込めて」シリーズ その69 

■問題 (出題者:にしお さん)
リストxsが渡されたときに

* 全部の要素が同じ値である(例:[1, 1, 1, 1])、
* 一つだけ仲間はずれがある(例:[1, 2, 1, 1, 1])、
* その他

を識別する関数を作ってください。 また判定後に「全部の要素が同じ値」の場合にはその値、 「一つだけ仲間はずれがある」の場合にはその仲間はずれの値と多数派の値を複雑な処理なしに取得できるようにしてください。
型にうるさい言語のために:リストの中身は非負の整数だと仮定して負の値を未定義値代わりに使っても構いません。
追記:リストの長さは3以上であると仮定して構いません。(2個で異なる値の時にどちらが仲間はずれか決まらないので。) nobsunさん、noriさん、ご指摘ありがとうございます。

この問題は、Linq to ObjectのGroupBy使えば良さそうですね。 
NakamaHazure というクラスを作成しています。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Doukaku.Org {
    class Program {
        static void Main(string[] args) {
            Execute(new int[] { 1, 1, 1, 1, 1 });
            Execute(new int[] { 1, 1, 1, 2, 1 });
            Execute(new int[] { 1, 1, 1, 2, 3 });
            Execute(new int[] { 1, 1, 1, 1, 1, 2, 1,1 ,1 });
            Console.ReadLine();
        }

        private static void Execute(IEnumerable<int> nums) {
            var nh = new NakamaHazure(nums);
            GroupType gt = nh.Classify();
            Console.Write(gt+ " ");
            if (gt == GroupType.LeftOut)
                Console.Write(nh.Divide());
            Console.WriteLine();
        }
    }

    public enum GroupType {
        Buddy,
        LeftOut,
        Mixed,
    }

    public class NakamaHazure {
        IGrouping<int, int>[] groups;
        public NakamaHazure (IEnumerable<int> nums) {
            groups = nums.GroupBy(x => x).ToArray();
        }

        public GroupType Classify() {
            if (groups.Length == 1)
                return GroupType.Buddy;
            if (groups.Length == 2 && groups.Count(n => n.Count() == 1) == 1)
                return GroupType.LeftOut;
            return GroupType.Mixed;
        }

        // Classify() == LeftOut のときのみ結果を保証する
        public Tuple<int,int> Divide() {
            var q = groups.OrderBy(x => x.Count());
            return Tuple.Create(
                q.First().Key,
                q.Skip(1).First().Key
            );
        }
    }
 }


 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52407160