大数据numbers优先级输出

来自MAKA后端笔试的一道题

问题

给一组长度巨大的整数 numbers 和 数值 M, 输出优先级最高的 M 个整数.

约定:

  • 偶数的优先级大于奇数
  • 同样是奇数(或偶数)，数值越小优先级越高
  • 算法时间复杂度最优

分析

  • 长度巨大, 因而需要考虑高精度数字
  • 偶数的优先级大于奇数, 这说明是需要进行奇偶的判断的, 可以想到需要分成两组数据
  • 数值越小优先级越高, 那么则是在同组内, 进行顺序排序
  • 算法时间复杂度最优, 那应该选快速排序, 在数据平均的情况下, 时间复杂度最低

代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
class Item
{
    public $length;
    public $data;

    /**
     * Item constructor.
     * @param string $number
     */
    public function __construct($number)
    {
        $this->length = strlen($number);
        $this->data   = $number;
    }

    public function isEven(): bool
    {
        return $this->data[$this->length - 1] % 2 === 0;
    }

    /**
     * @param Item $b
     * @return int
     */
    public function compareWith(Item $b): int
    {
        if ($this->length > $b->length) {
            return 1;
        }
        if ($this->length < $b->length) {
            return -1;
        }

        $result = 0;
        for ($i = 0; $i < $this->length; $i++) {
            if ($this->data[$i] > $b->data[$i]) {
                $result++;
            }
            if ($this->data[$i] < $b->data[$i]) {
                $result--;
            }
        }
        if ($result > 0) {
            return 1;
        }
        if ($result < 0) {
            return -1;
        }
        return 0;
    }
}

/**
 * @param Item[] $arr
 * @return Item[]
 */
function quickSort(array $arr)
{
    $count = count($arr);

    if ($count < 2) {
        return $arr;
    }

    $left = $right = [];
    // 基准值
    $middle = $arr[0];

    for ($i = 1; $i < $count; $i++) {
        // 小于基准值，存入左边；大于基准值，存入右边
        if ($arr[$i]->compareWith($middle) < 0) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }

    $left  = quickSort($left);
    $right = quickSort($right);

    // 顺序
    return array_merge($left, [$middle], $right);
    // 降序
//     return array_merge($right, [$middle], $left);
}

function run($numbers, $M)
{
    $odd  = [];
    $even = [];

    foreach ($numbers as $number) {
        $number = new Item($number);
        if ($number->isEven()) {
            $even[] = $number;
        } else {
            $odd[] = $number;
        }
    }

    // TODO: 这里其实还可以再根据 M 来做一些小优化的

    foreach (quickSort($even) as $item) {
        echo $item->data . ' ';
        $M--;
        if ($M === 0) {
            echo PHP_EOL;
            return;
        }
    }

    foreach (quickSort($odd) as $item) {
        echo $item->data . ' ';
        $M--;
        if ($M === 0) {
            echo PHP_EOL;
            return;
        }
    }

    echo PHP_EOL;
}

run(['6', '7', '3', '5', '4', '2', '3', '3', '1'], 3);