Distinct #PHP

今回から、ちゃんと reading material を読みます。

reading material

概要だけ記します。
ソートとは、数字やアルファベットの順にある組を並べることです。
色々なやり方があり、計算量やメモリの使用量に差異があります。
例として、選択ソート、分布数え上げソート、マージソートが挙げられており、Python では組み込みの
sort 関数があることを付記しています。

1st

これは PHP の組み込み関数をフル活用しとるから、卑怯かもしれん。
（アイデア勝負ではない点で。アルゴリズムを考えるべき。）

Correctness	Performance	Task Score
100%	100%	100%

Distinct-1.php

function solution($A) {
    $unique = array_unique($A);
    $aligned = array_values($unique);
    return count($aligned);
}

組み込み関数を使うと、最適化された計算量になることは見込まれるけど、内部の処理に思いを馳せられ
んから、やっぱ自分で実装しよう。

2nd

Correctness	Performance	Task Score
33%	0%	25%

Distinct-2.php

function solution($A) {
    $count = 0;
    $array = array_fill(0, count($A), 0);

    // 配列の要素に該当する場所に１をセットする
    foreach($A as $value) {
        if(! $array[$value]) {
            $array[$value] = 1;
        }
    }
    // １がセットされている箇所を数える
    foreach($array as $value) {
        if($array[$value]) {
            $count++;
        }
    }

    return $count;

}

TestDistinct-2.php

include 'Distinct-2.php';

class DistinctTest extends \PHPUnit\Framework\TestCase {

    public function testDistinct() {
        $array = array(2, 1, 1, 2, 3, 1);
        $ans = solution($array); $this->assertEquals(3, $ans);

        $array = array(1, 1, 5, 2, 3, 4);
        $ans = solution($array); $this->assertEquals(5, $ans);
    }

}

所詮実力はこんなもんやった。問題をよく読んでいないことが露呈した。なんせ、前提として、

each element of array A is an integer within the range [−1,000,000..1,000,000].

やから。つまり、負の数を考慮出来てない。どうやらこのマッピング手法ではダメか？
というわけで、最初の解答で終わりにし、お手本を見るとする。

お手本１

なんと、兼ねてよりお世話になっていた jimii さんは、Lesson 6 以上を Github にあげていない！
よって、まずは miina さんをお手本とする。

miina さんの提出した（らしき）コードは、return count(array_unique($A)); 。
ま、やっぱりこれよな。

ただし、コメントで、その他に３通りの解き方を書いてくれとる。
つまり、以下の４つの解き方が書いてある。

return count(array_unique($A));
return count(array_count_values($A));
return count(array_flip($A));
マッピング手法（後述）

array_count_values は、要素ごとの出現回数を数えるから、返り値の配列は重複が無くなっている。
array_flip は、副作用を利用した解法。この関数は、キーと値の反転時に、重複を消す副作用がある。
そして、マッピング手法は、以下に自分で解いたコードを記すため、これで理解して欲しい。

マッピング手法による解答

Correctness	Performance	Task Score
100%	100%	100%

Distinct-3.php

function solution($A) {
    $array = array();

    foreach($A as $value) {
        if(! isset($array[$value])) {
            $array[$value] = 1;
        }
    }

    return count($array);
}

count を使わず for で数え上げてもいいが、与えられた配列の要素をキーとして、キーが存在
しなければ、それをキーとして１を値に持つ要素を配列に追加し、存在すれば何もしない。
ループ終了後は、$arrayの count が the number of distinct values になる。

miina さん、参考になりました。ありがとう。

ところで、この問題が sorting のジャンルなのは何故だろうか。