仲間はずれの判定 in C DouKaku?

仲間はずれの判定

リストxsが渡されたときに

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

を識別する関数を作ってください。また判定後に「全部の要素が同じ値」の場合にはその値、「一つだけ仲間はずれがある」の場合にはその仲間はずれの値と多数派の値を複雑な処理なしに取得できるようにしてください。

型にうるさい言語のために：リストの中身は非負の整数だと仮定して負の値を未定義値代わりに使っても構いません。

追記：リストの長さは3以上であると仮定して構いません。(2個で異なる値の時にどちらが仲間はずれか決まらないので。) nobsunさん、noriさん、ご指摘ありがとうございます。

もっとスリム化できそうですがとりあえず。

import java.util.*;
public class NakamaHazure {
    public static void main(String[] args) {
        check(Arrays.asList(1,1,1,1));    // => [1]
        check(Arrays.asList(1,2,1,1,1));    // => [2,1]
        check(Arrays.asList(1,2,2,1,1));    // => []
        check(Arrays.asList(1,2,2,1,3));    // => []
    }
    private static void check(List<Integer> list) {
        HashSet<Integer> set = new HashSet<Integer>();
        HashSet<Integer> minor = new HashSet<Integer>();;
        Integer major = null;
        for (Integer i : list) {
            if (!set.add(i)) {
                if (major != null && major != i) {
                    System.out.println("[]");
                    return;
                }
                minor.remove(i);
                major = i;
            } else {
                minor.add(i);
            }
        }
        if (set.size() == 1) {
            System.out.println("[" + set.iterator().next() + "]");
        } else if (set.size() == 2) {
            System.out.println("[" + minor.iterator().next() + "," + major + "]");
        } else {
            System.out.println("[]");
        }
    }
}

array_count_values便利ですね。あえて使わないで作ってみる事で便利さを際実感

$a[]= array(1,1,1,1);#1
$a[]= array(1,2,1,1,1);#2
$a[]= array(2,1,2,2);#その他
$a[]= array(1,2,2,2);#その他
$a[]= array(1,1,2,2);#その他
$a[]= array(1,1,2,3);#その他
function check($_array){
    $uniques = sizeof(array_unique($_array));
    switch($uniques){
        case(1):
            return array("仲間"=>array_pop($_array));
        case(2):
            sort($_array);
            #仲間はずれ
            if( $_array[0]!=$_array[1] ){
                return array( "仲間はずれ"=>array_shift($_array),"仲間"=>array_pop($_array) );
            }else if($_array[0]==$_array[1] && $_array[sizeof($_array)-1] != $_array[sizeof($_array)-2] ){
                return array( "仲間はずれ"=>array_pop($_array),"仲間"=>array_shift($_array) );
            }
        default:
            return "その他";
    }


}

foreach( $a as $b ){
    print_r( check($b) ).PHP_EOL;
}

post comment

Posted feedbacks - C

#include <stdio.h>
enum { hetero, homo, quasi_homo };
typedef struct {
    int type;                   /* hetero, homo, quasi_homo */
    int one;
    int other;
} classify_result;

classify_result classify(int *p, int len) {
    int temp[] = {  -1,  0,  -1,    0 };
    /*            key1 val1 key2 val2 */
    int cur, i;
    static classify_result hetero_result = {hetero, -1, -1};
    classify_result res = hetero_result;

    if (len == 0) return hetero_result;
    for (i=0; i<len; i++) {
        cur = p[i];
        if (temp[0] == cur) temp[1]++;
        else if (temp[2] == cur) temp[3]++;
        else if (temp[0] == -1) { temp[0]=cur; temp[1]=1; }
        else if (temp[2] == -1) { temp[2]=cur; temp[3]=1; }
        else return hetero_result;
    }
    if (temp[2] == -1) { res.type = homo; res.one = temp[1]; }
    else if (temp[1] == 1) { res.type = quasi_homo; res.one = temp[0]; res.other = temp[2]; }
    else if (temp[3] == 1) { res.type = quasi_homo; res.one = temp[2]; res.other = temp[0]; }
    else return hetero_result;
    return res;
}
/* コードはここまで。以後テスト。 */

void print_classify_result(classify_result x) {
    switch(x.type) {
    case hetero:
        printf("<hetero>\n");
        break;
    case homo:
        printf("<homo %d>\n", x.one);
        break;
    case quasi_homo:
        printf("<quasi_homo %d %d>\n", x.one, x.other);
        break;
    default:
        printf("BUG!\n");
    }
}
int main() {
    {
        int ary[] = {1,1,1,1};
        print_classify_result(classify(ary, sizeof(ary)/sizeof(int)));
    }
    {
        int ary[] = {1,2,1,1,1};
        print_classify_result(classify(ary, sizeof(ary)/sizeof(int)));
    }
    {
        int ary[] = {1,1,1,1,2};
        print_classify_result(classify(ary, sizeof(ary)/sizeof(int)));
    }
    {
        int ary[] = {2,2,1,1,1,1};
        print_classify_result(classify(ary, sizeof(ary)/sizeof(int)));
    }
    {
        int ary[] = {2,4,1,1,1,1};
        print_classify_result(classify(ary, sizeof(ary)/sizeof(int)));
    }
    {
        int ary[] = {1,2,3,4};
        print_classify_result(classify(ary, sizeof(ary)/sizeof(int)));
    }
    {
        int ary[] = {};
        print_classify_result(classify(ary, sizeof(ary)/sizeof(int)));
    }
}

非負整数を仮定して、識別結果を、以下のようにしました。
全部同じ場合：major=x, minor=-1
一つだけ仲間はずれ：major=x, minor=y
その他：major=-1, minor=-1
最初の３つで、重複する値を先に決めてしまう方法で。

#include <stdio.h>

struct group { int major; int minor; };

struct group group_check(int *n, int len) {
	int i;
	struct group g = { -1, -1 };

	if (len < 3) return g;

	if (n[0] == n[1] || n[0] == n[2]) g.major = n[0];
	else if (n[1] == n[2]) g.major = n[1];
	else return g;
	
	for (i = 0; i < len; i++) {
		if (g.major == n[i]) continue;
		if (g.minor == -1) g.minor = n[i];
		else { g.major = -1; g.minor = -1; break; }
	}
	return g;
}

int main() {
	struct group g;
	int n[] = { 1, 2, 1, 1, 1, 1 };
	g = group_check(n, sizeof(n) / sizeof(n[0]));
	printf("major=%d minor=%d\n", g.major, g.minor);
	return 0;
}

DouKaku?

仲間はずれの判定

Posted feedbacks - C

Index

Feed

Other

Link

Pathtraq