leetcode-php/src/leetcode/TopKFrequentElements.php at master · imajinyun/leetcode-php · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
<?php

declare(strict_types=1);

namespace leetcode;

class TopKFrequentElements
{
    public static function topKFrequent(array $nums, int $k): array
    {
        if (empty($nums) || $k <= 0) {
            return [];
        }
        $map = array_count_values($nums);
        arsort($map);

        $keys = array_keys($map);
        if ($k > count($map)) {
            return $keys;
        }

        return array_slice($keys, 0, $k);
    }

    public static function topKFrequent2(array $nums, int $k): array
    {
        if (empty($nums) || $k <= 0) {
            return [];
        }
        $ans = $map = [];
        foreach ($nums as $num) {
            $map[$num] = ($map[$num] ?? 0) + 1;
        }
        arsort($map);

        $keys = array_keys($map);
        if ($k > count($map)) {
            return $keys;
        }

        for ($i = 0; $i < $k; $i++) {
            array_push($ans, array_shift($keys));
        }

        return $ans;
    }

    public static function topKFrequent3(array $nums, int $k): array
    {
        if (empty($nums) || $k <= 0) {
            return [];
        }
        $ans = $map = [];
        $map = array_count_values($nums);
        $heap = new \SplPriorityQueue();
        foreach ($map as $key => $val) {
            $heap->insert($key, $val);
        }
        for ($i = 0; $i < $k; $i++) {
            array_push($ans, $heap->extract());
        }

        return $ans;
    }
}