-1

我有一个数组数组：

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

我怎样才能做到这一点？

4

4 回答 4

2

我通过将元素过滤到 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);

在此处查看此演示。

于 2019-08-19T03:02:31.870 回答
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,
  ),
)
于 2019-08-19T03:08:30.527 回答
1

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

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

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

代码：（演示）

$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);
于 2020-10-10T07:54:21.943 回答
1

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

于 2019-08-19T03:41:15.877 回答