php - 标记未排序数组的前 N ​​个元素

Question

我有一个未排序的数组(生成的骰子)，我想选择它的前 N ​​个元素(这对于排序和剪断来说很简单)，但在保持它们有序的同时标记它们。

例如:

mark([1,2,3,4], 3) ==> [[1, false], [2, true], [3, true], [4, true]]

mark([3,5,2,6,2], 3) ==> [[3, true], [5, true], [2, false], [6, true], [2, false]]

数组可以包含从 1 开始的任意值，任意长度，标记元素的数量是可变的。

我可以忍受

mark([3,5,2,6,2], 3) ==> [[3, true], [5, true], 2, [6, true], [2, true]]

(即，标记为假的数字未标记)，但我宁愿避免它。

强制性的是数组的顺序保持不变。

如果顶部元素重复(例如:[6,6,6,6,6,6] 的前 3 个)，标记前 3 个元素。

(N 足够小，复杂度无关紧要。)

编辑:奖励点:添加一个参数以在“顶部”和“底部”模式之间切换。

Answer 1

我假设我们在这里讨论的是 PHP，因为这个问题被标记为 PHP。您将尝试实现的任何巧妙算法都将比使用内置函数慢。这就是 PHP 的工作方式，它不擅长处理用户空间中的数字。

所以你需要做的是对数组的副本进行排序并保存前 N 个元素的键，然后遍历数组并标记所述元素。但是有一个问题:PHP 的排序并不稳定。这意味着如果你想在平局的情况下使用元素的位置，你必须自己做。因此，不要使用诸如 asort() 之类的函数或 arsort() , 你必须使用 array_multisort() .

结果是这样的:

function mark(array $arr, $n, $order = SORT_DESC)
{
    $keys = $values = $position = array();

    $i = 0;
    foreach ($arr as $k => $v)
    {
        $keys[]     = $k;
        $values[]   = $v;
        $position[] = $i;

        ++$i;
    }

    // sort values in given $order, use their position as tiebreaker (always in ascending order)
    array_multisort($values, $order, $position, SORT_ASC, $keys);
    $mark = array_flip(array_slice($keys, 0, $n));

    $ret = array();
    foreach ($arr as $k => $v)
    {
        $ret[] = array($v, isset($mark[$k]));
    }

    return $ret;
}

产生

SORT_DESC
[3,6,6,6,6,6,2] => [[3,false],[6,true],[6,true],[6,true],[6,false],[6,false],[2,false]]
[3,5,2,6,2]     => [[3,true],[5,true],[2,false],[6,true],[2,false]]

SORT_ASC
[3,6,6,6,6,6,2] => [[3,true],[6,true],[6,false],[6,false],[6,false],[6,false],[2,true]]
[3,5,2,6,2]     => [[3,true],[5,false],[2,true],[6,false],[2,true]]