如何通过交替“性别”值对关联数组的数组进行排序？

Question

我有一个数组数组：$students= array(    array("name"=>"...", "gender"=>"male"),    array("name"=>"...", "gender"=>"female"),    array("name"=>"...", "gender"=>"female"),    array("name"=>"...", "gender"=>"female"),    array("name"=>"...", "gender"=>"male"),    array("name"=>"...", "gender"=>"male"),    array("name"=>"...", "gender"=>"male"),);我想$students通过交替性别对元素进行排序以获得：$students= array(    array("name"=>"...", "gender"=>"male"),    array("name"=>"...", "gender"=>"female"),    array("name"=>"...", "gender"=>"male"),    array("name"=>"...", "gender"=>"female"),    array("name"=>"...", "gender"=>"male"),    array("name"=>"...", "gender"=>"female"),    array("name"=>"...", "gender"=>"male"),);我怎样才能做到这一点？

Answer 1

我通过将元素过滤到 2 个单独的数组 ($males和$females)来做到这一点。array_filter保留键，所以我们只需将它传递array_values给从 0 开始的新键列表。从那里开始，这是一个简单的 for 循环，将它们交织在一起并将它们添加到最终数组中。

<?php

$students= [

    ["name"=>"...", "gender"=>"male"],

    ["name"=>"...", "gender"=>"female"],

    ["name"=>"...", "gender"=>"female"],

    ["name"=>"...", "gender"=>"female"],

    ["name"=>"...", "gender"=>"male"],

    ["name"=>"...", "gender"=>"male"],

    ["name"=>"...", "gender"=>"male"],

];

$males = array_values(array_filter($students, function($s) { return $s["gender"] === "male"; }));

$females = array_values(array_filter($students, function($s) { return $s["gender"] === "female"; }));

$final = [];

$max = max(count($females), count($males));

for ($i=0; $i<$max; $i++) {

    if (isset($males[$i])) {

        $final[] = $males[$i];

    }

    if (isset($females[$i])) {

        $final[] = $females[$i];

    }

}

print_r($final);

Answer 2

天真的解决方案

您可以使用array_filter根据性别创建两个组。然后使用将组压缩成对array_map并运行对array_reduce以压平结构：

$males = array_filter($students, function ($e) {

    return $e["gender"] === "male";

});

$females = array_filter($students, function ($e) {

    return $e["gender"] === "female";

});

$zipped = array_map(null, $males, $females);

$result = array_reduce($zipped, function ($a, $e) {

    if ($e[0]) $a[] = $e[0];

    if ($e[1]) $a[] = $e[1];

    return $a;  

}, []);

时间复杂度为 O(n)。

减少开销

如果第一个解决方案的开销太大，请考虑消除函数调用。它仍然是 O(n) 两次传递，但分支预测应该处理合并循环中性别之间存在广泛数量不平衡的情况：

foreach ($students as $student) {

    if ($student["gender"] === "male") {

        $males[]= $student;

    }

    else {

        $females[]= $student;

    }

}

$male_count = count($males);

$female_count = count($females);

for ($i = 0, $j = 0; $i < $male_count || $j < $female_count;) {

    if ($i < count($males)) {

        $result[]= $males[$i++];

    }

    if ($j < count($females)) {

        $result[]= $females[$j++];

    }

}

概括

上面的代码假设两件事：（1）"male"即使它产生次优交错（根据OP 的规范）也应该始终是第一个；（2）只"gender"存在两个值。

第一个问题可以通过修改上面的代码片段在压缩阶段交换数组顺序以优先选择最长的数组来解决。

可以使用array_reduce为目标键的每个唯一值创建数组元素的分组来解决第二个问题，然后删除硬编码值以支持对这些按频率降序排序的组进行迭代（可以添加打破平局的逻辑）。

以下代码的时间复杂度为 O(n + k*log(k))，其中k是唯一值的数量。最坏的情况是，所有条目都是完全或几乎唯一的，在这种情况下，由于多余的排序，我们有一个 O(n log(n)) 解决方案，但如果k是常数，则为 O(n) ，就像在 OP 的情况下一样。

请注意，PHP 排序例程不稳定，因此您需要将数组打包和解压缩为索引/元素对，或者使用索引以外的自定义打破平局策略。

<?php

function interleave_values($arr, $key) {

    $unique_values = array_unique(array_column($arr, $key));

    $buckets = array_reduce($arr, function ($a, $e) use ($key) {

        $a[$e[$key]][] = $e;

        return $a;

    }, []);

    rsort($buckets);

    $zipped = array_map(null, ...$buckets);

    return array_reduce($zipped, function ($a, $e) {

        foreach ($e as $f) {

            if (!$f) break;

            $a[] = $f;

        }

        return $a;  

    }, []);

}

$test = [

    ["k" => 1],

    ["k" => 2],

    ["k" => 1],

    ["k" => 3],

    ["k" => 3],

    ["k" => 1],

    ["k" => 2],

    ["k" => 2],

    ["k" => 2],

];

var_export(interleave_values($test, "k"));

输出：

array (

  0 => 

  array (

    'k' => 2,

  ),

  1 => 

  array (

    'k' => 1,

  ),

  2 => 

  array (

    'k' => 3,

  ),

  3 => 

  array (

    'k' => 2,

  ),

  4 => 

  array (

    'k' => 1,

  ),

  5 => 

  array (

    'k' => 3,

  ),

  6 => 

  array (

    'k' => 2,

  ),

  7 => 

  array (

    'k' => 1,

  ),

  8 => 

  array (

    'k' => 2,

  ),

)

Answer 3

我不认为我建议创建临时的特定于性别的数组，然后将它们拉链合并。

我喜欢维护两个特定于性别的计数器并且只在一个循环中迭代它们的效率。我的循环不进行内部函数调用。

事实上，确定哪个性别应该先出现需要比新的关键分配更多的处理。

代码：

$students = [

    ["name" => "...", "gender" => "male"],

    ["name" => "...", "gender" => "female"],

    ["name" => "...", "gender" => "female"],

    ["name" => "...", "gender" => "female"],

    ["name" => "...", "gender" => "male"],

    ["name" => "...", "gender" => "male"],

    ["name" => "...", "gender" => "male"],

];

$counters = ['female' => 1, 'male' => 1];

// determine which gender should start from 0

$genderCounts = array_count_values(

    array_column($students, 'gender')

);

arsort($genderCounts);

--$counters[key($genderCounts)];

// assign keys

$result = [];

foreach ($students as $student) {

    $gender = $student['gender'];

    $result[$counters[$gender]] = $student;

    $counters[$gender] += 2;

}

ksort($result);

var_export($result);