如何按交替值对关联数组的数组进行排序？

Question

我有一个数组的数组：

$students= [
    ["name"=>"...", "classroom"=>"red"],
    ["name"=>"...", "classroom"=>"red"],
    ["name"=>"...", "classroom"=>"blue"],
    ["name"=>"...", "classroom"=>"blue"],
    ["name"=>"...", "classroom"=>"blue]",
    ["name"=>"...", "classroom"=>"red"],
    ["name"=>"...", "classroom"=>"red"],
    ["name"=>"...", "classroom"=>"red"],
];

我想通过交替教室对

$students

元素进行排序以获得：

$students= [
    ["name"=>"...", "classroom"=>"red"],
    ["name"=>"...", "classroom"=>"blue"],
    ["name"=>"...", "classroom"=>"red"],
    ["name"=>"...", "classroom"=>"blue"],
    ["name"=>"...", "classroom"=>"red"],
    ["name"=>"...", "classroom"=>"blue]",
    ["name"=>"...", "classroom"=>"red"],
    ["name"=>"...", "classroom"=>"red"],
];

如果数量为奇数，剩余的值应放在最后。

我该怎么做？

Answer 1

简单的解决方案

您可以使用

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))，其中

是唯一值的数量。最坏的情况是，所有条目完全或几乎是唯一的，在这种情况下，由于多余的排序，我们有一个 O(n log(n)) 解决方案，但如果

是常数，则它是 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 2

我通过将元素过滤到 2 个单独的数组（

$reds

和

$blues

）来做到这一点。

array_filter

保留键，因此我们只需将其传递给

array_values

即可获取从 0 开始的新键列表。从那里开始，这是一个简单的 for 循环，将它们交织在一起并将它们添加到最终数组中。

<?php

$students= [
    ["name"=>"...", "classroom"=>"red"],
    ["name"=>"...", "classroom"=>"blue"],
    ["name"=>"...", "classroom"=>"blue"],
    ["name"=>"...", "classroom"=>"blue"],
    ["name"=>"...", "classroom"=>"red"],
    ["name"=>"...", "classroom"=>"red"],
    ["name"=>"...", "classroom"=>"red"],
];

$reds = array_values(array_filter($students, function($s) { return $s["classroom"] === "red"; }));
$blues = array_values(array_filter($students, function($s) { return $s["classroom"] === "blue"; }));

$final = [];
$max = max(count($blues), count($reds));

for ($i=0; $i<$max; $i++) {
    if (isset($reds[$i])) {
        $final[] = $reds[$i];
    }
    
    if (isset($blues[$i])) {
        $final[] = $blues[$i];
    }
}

print_r($final);

请参阅此演示此处。

Answer 3

Array_filter 会遍历数组，仅仅为了分割数组而这样做两次是不必要的。
相反，用 foreach 循环它并分割它。
然后 array_combine 每个部分具有偶数或奇数数字键并将两者合并。

foreach($students as $stu){
    if($stu['gender'] == 'male'){
        $male[] = $stu;
    }else{
        $female[] = $stu;
    }
}


$male = array_combine(range(0,(count($male)-1)*2,2),$male); // make keys even starting with 0
$female = array_combine(range(1,count($female)*2,2),$female); // make keys uneven starting with 1
$all = array_replace($male, $female); // replace can be used since they keys do not create any problems
ksort($all); //sort on key
$all = array_values($all);

var_dump($all);

https://3v4l.org/TZCKN

另一种方法是在 foreach 中分配键，然后执行 array_replace。
这应该会更快，因为涉及的数组函数更少。

$i = 0;
$j = 1;
foreach($students as $stu){
    if($stu['gender'] == 'male'){
        $male[$i] = $stu;
        $i +=2;
    }else{
        $female[$j] = $stu;
        $j +=2;
    }
}

$all = array_replace($male, $female);
ksort($all);
$all = array_values($all);

var_dump($all);

https://3v4l.org/k3MMj

Answer 4

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

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

事实上，确定哪种性别应该放在第一位需要比新的关键任务更多的处理。

代码：（演示）

$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);

另一种方法是利用一系列特定于性别的计数器，按每个独特性别的遭遇进行排序。当在每个遭遇组中打破平局时，此脚本将优先考虑

male

在

female

之前。仅当您提前知道每个组应如何排序时，此方法才适用。演示

$array = [
    ["name" => "a", "gender" => "male"],
    ["name" => "b", "gender" => "female"],
    ["name" => "c", "gender" => "female"],
    ["name" => "d", "gender" => "female"],
    ["name" => "e", "gender" => "male"],
    ["name" => "f", "gender" => "male"],
    ["name" => "g", "gender" => "male"],
];

$nths = [];
$genders = [];
foreach ($array as ['gender' => $v]) {
    $genders[] = $v;
    $nths[] = $counters[$v] = ($counters[$v] ?? 0) + 1;
}

array_multisort(
    $nths, /* prioritize by order of encounter per unique gender */
    $genders, /* sort by gender per encounter group */
    SORT_DESC, /* sort "male" before "female" per encounter group */
    $array /* break any remaining ties and modify the original array */
);
var_export($array);

第二个片段类似于我的另一个答案（以重复的升序对平面数组进行排序），其设计用于“每轮”容纳两个以上的唯一值。

如果出于时间复杂性原因您想避免使用排序函数，并且您可以预设每轮性别的顺序，您可以按两个预测的性别值进行分组，然后临时映射对并在一个性别出现时回退到空数组值不足，然后解压并合并有效负载。演示

$grouped = ['male' => [], 'female' => []];
foreach ($students as $student) {
    $grouped[$student["gender"]][] = $student;
}

var_export(
    array_merge(
        ...array_map(
            fn($m, $f) => [$m ?? [], $f ?? []],
            $grouped['male'],
            $grouped['female']
        )
    )
);

如何按交替值对关联数组的数组进行排序？

问题描述投票：0回答：4

4个回答

简单的解决方案

减少开销

概括

最新问题

如何按交替值对关联数组的数组进行排序？

问题描述 投票：0回答：4

4个回答

简单的解决方案

减少开销

概括

最新问题

问题描述投票：0回答：4