Help us understand the problem. What is going on with this article?

Distinct

More than 1 year has passed since last update.

今回から、ちゃんと 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);

    // 配列の要素に該当する場所に1をセットする
    foreach($A as $value) {
        if(! $array[$value]) {
            $array[$value] = 1;
        }
    }
    // 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].

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

お手本1

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

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

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

  1. return count(array_unique($A));
  2. return count(array_count_values($A));
  3. return count(array_flip($A));
  4. マッピング手法(後述)

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 で数え上げてもいいが、与えられた配列の要素をキーとして、キーが存在
しなければ、それをキーとして1を値に持つ要素を配列に追加し、存在すれば何もしない。
ループ終了後は、$arraycount が the number of distinct values になる。

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

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

geckothic
PHP(CodeIgniter), JS(jQuery), Go, Google Cloud Platform
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away