仲間はずれの判定 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++

総て同じなら value1 にその値が入り、仲間外れがいればその値が value1 に、その他が value2 に入る。それ以外の value[1/2] は、無効な値（デフォルトコンストラクタの返す値）が入る。

a.txt というファイルに
1 1 1 1
1 2 1 1 1
のように各行に数字を空白で区切って保存すると、そこから読み込むようにした。

#include <iostream>
#include <fstream>
#include <sstream>
#include <iterator>
#include <algorithm>
#include <functional>
#include <vector>

enum result_type { all, alone, other };

template <typename T>
struct result
{
    result_type type;

    T value1, value2;

    result(result_type type_, const T& value1_ = T(), const T& value2_ = T())
        : type(type_), value1(value1_), value2(value2_) {}
};

template <typename T>
result<T> judge(const std::vector<T>& v)
{
#define not_equal_to(x) std::not1(std::bind1st(std::equal_to<T>(), x))

    if (v.size() >= 3)
    {
        std::vector<T>::const_iterator it = std::find_if(v.begin() + 1, v.end(), not_equal_to(v[0]));

        if (it == v.end())
        {
            return result<T>(all, v[0]);
        }

        if (it == v.begin() + 1 && std::find_if(it + 1, v.end(), not_equal_to(*it)) == v.end())
        {
            return result<T>(alone, v[0], *it);
        }

        if (std::find_if(it + 1, v.end(), not_equal_to(v[0])) == v.end())
        {
            return result<T>(alone, *it, v[0]);
        }
    }

    return result<T>(other);

#undef not_equal_to
}

template <typename T>
void solve(const std::vector<T>& v)
{
    const result<T> r = judge(v);

    if (r.type == all)
    {
        std::cout << "all: " << r.value1 << std::endl;
    }
    else if (r.type == alone)
    {
        std::cout << "alone: " << r.value1 << " " << r.value2 << std::endl;
    }
    else
    {
        std::cout << "other" << std::endl;
    }
}

int main()
{
    std::ifstream fin("a.txt");

    std::string line;

    while (std::getline(fin, line))
    {
        std::istringstream sin(line);

        std::istream_iterator<int> beg(sin), end;

        solve(std::vector<int>(beg, end));
    }
}

DouKaku?

仲間はずれの判定

Posted feedbacks - C++

Index

Feed

Other

Link

Pathtraq