我有一个月份数组（数字，1-12），我想对它们进行排序，这将构成最大的连续序列。一个例子：
array(1,2,3)：
很简单，就是一月到三月，不需要排序
array(1,2,11,12)：
这可能是 11 月至 2 月的一个连续序列，因此应按 11、12、1、2 进行排序
array(1,4,5,11,12)：
这应该是 4-5 月，11-1 月，所以应该分成两部分：4,5 和 11,12,1
任何想法如何做到这一点？
问问题
216 次
5 回答
2
一旦你弄清楚如何表达12可以环绕的事实，这很容易做到1。
这是我的解决方案。它自然地对传入的数组进行排序，然后创建一个$months如下所示的数组：
$months = 1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6 7 8 9 10 11 12
从该数组中，我循环输入数组以在未设置月份值的位置放置零。因此，输入数组array( 1, 2, 11, 12)，$inputs数组变为：
$inputs = 1 2 0 0 0 0 0 0 0 0 11 12 1 2 0 0 0 0 0 0 0 0 11 12
从这里开始，算法很简单：遍历$inputs数组以找到非 0 的最长序列。这将生成所有可能的顺序序列。
function sort_months( $array)
{
natsort( $array);
$keys = array_flip( $array);
$inputs = array();
$months = array_merge( range( 1, 12), range( 1, 12));
foreach( $months as $m) {
$inputs[] = (isset( $keys[$m])) ? $m : 0;
}
$sequences = array();
for( $i = 0, $ii = count( $inputs); $i < $ii; $i++) {
if( $inputs[$i] != 0) {
$sequence = array( $inputs[$i]);
for( $k = $i + 1, $kk = $ii + 1; $k < $kk; $sequence[] = $inputs[$k], $k++) {
if( !isset( $inputs[$k]) || $inputs[$k] == 0) {
break;
}
}
$sequences[] = $sequence;
}
}
return $sequences;
}
使用输入array( 12, 11, 1, 2)，这将输出：
array(8) {
[0]=>
array(2) {
[0]=>
int(1)
[1]=>
int(2)
}
[1]=>
array(1) {
[0]=>
int(2)
}
[2]=>
array(4) {
[0]=>
int(11)
[1]=>
int(12)
[2]=>
int(1)
[3]=>
int(2)
}
[3]=>
array(3) {
[0]=>
int(12)
[1]=>
int(1)
[2]=>
int(2)
}
[4]=>
array(2) {
[0]=>
int(1)
[1]=>
int(2)
}
[5]=>
array(1) {
[0]=>
int(2)
}
[6]=>
array(2) {
[0]=>
int(11)
[1]=>
int(12)
}
[7]=>
array(1) {
[0]=>
int(12)
}
}
您可以看到最长的顺序序列实际上存在于数组中（以及所有其他可能的序列）：
[2]=>
array(4) {
[0]=>
int(11)
[1]=>
int(12)
[2]=>
int(1)
[3]=>
int(2)
}
我将其留给 OP 来确定如何选择要使用哪些序列来表示输入到该函数的所有月份。
于 2012-07-20T14:06:50.683 回答
2
查看您的数据，我们看到以下先决条件：
- 最大范围是 1 到 12。
- 输入是排序的，因此是有序的。
- 只有一个地方发生了环绕：从 12 点到 1 点。
考虑到这一点，我们可以说：
- 第一个值为 1 或没有环绕。
- 最后一个值为 12 或没有环绕。
- 如果有环绕，则从开始 (1,2,...) 开始的所有连续月份都会环绕。
这是一个相对简单的功能：
function group_months(array $months) {
$count = count($months);
if (!$count || $months[0] != 1 || $months[$count-1] != 12 || $count === 12) {
return $months;
}
for ($size = 1; $months[$size] === $size+1;) {
$size++;
}
return array_merge(array_slice($months, $size), range(1, $size));
}
或者在 shift-push 变体中（移动 1,2,... 到结束）：
function group_months(array $months)
{
$count = count($months);
if ($count && $count != 12 && $months[$count - 1] === 12) {
for ($month = 1; $months[0] === $month; $month++) {
$months[] = array_shift($months);
}
}
return $months;
}
或者在 pop-unshift 变体中（将 ..,11,12 移到前面）：
function group_months(array $months)
{
$count = count($months);
if ($count-- && $count != 11 && $months[0] === 1) {
for ($month = 12; $months[$count] === $month; $month--) {
array_unshift($months, array_pop($months));
}
}
return $months;
}
如果您想对数组中的数字进行分组，请参阅已经有字符串输出解决方案的相关问题：
于 2012-07-21T20:33:55.953 回答
1
Try the PHP function below. It works fine with all 3 examples given:
<pre>
<?php
function split_months($array)
{
// remove duplicate values, if any
// sort the array in ascending order
$array = array_unique($array);
sort($array);
$results = array();
// loop until the array is empty
while(!empty($array))
{
// extract the first entry of the array
$entry = array_shift($array);
if(empty($results))
$results[] = array($entry);
else
{
// find in which sub-array of $results $entry needs to be stored
foreach($results as $index => $values)
{
// extract the last value
$last = array_pop($values);
// compare with $entry
if($entry-1 == $last)
{
$results[$index][] = $entry;
unset($entry);
break;
}
}
// there was no sub-array to store $entry: store it in a new sub-array
if(isset($entry))
$results[] = array($entry);
}
}
// if $results contain no array, or only one, there is nothing to optimize
if(sizeof($results) <= 1)
return $results;
// lastly, search if one result sub-array is starting with "1", and another is ending with "12"
// in that case, join these 2 sub-arrays in one
foreach($results as $index => $values)
{
if($values[0] == 1)
$index1 = $index;
elseif($values[sizeof($values)-1] == 12)
$index12 = $index;
if(isset($index1) && isset($index12))
break;
}
if(isset($index1) && isset($index12))
{
// merge both sub-arrays
$results[$index12] = array_merge($results[$index12], $results[$index1]);
// remove the sub-array starting with "1"
unset($results[$index1]);
}
return $results;
}
$array1 = array(1,2,3);
$array2 = array(1,2,11,12);
$array3 = array(1,4,5,11,12);
print_r(split_months($array1));
print_r(split_months($array2));
print_r(split_months($array3));
?>
</pre>
The output will be:
Array
(
[0] => Array
(
[0] => 1
[1] => 2
[2] => 3
)
)
Array
(
[1] => Array
(
[0] => 11
[1] => 12
[2] => 1
[3] => 2
)
)
Array
(
[1] => Array
(
[0] => 4
[1] => 5
)
[2] => Array
(
[0] => 11
[1] => 12
[2] => 1
)
)
于 2012-07-20T14:14:55.347 回答
1
我的 PHP 不足以编写实现，但我很想知道这是否可以通过使用循环数组或链接列表结构来实现。
next首先，创建这样一个包含 12 个布尔元素的结构，通过将最终元素的属性设置为第一个元素来使其成为圆形。相反，第previous一个元素被设置为最后一个元素。这代表您的“环绕式”日历。
然后，您可以读取数组，将“日历”的每个元素设置true为元素索引出现在输入数组中的位置。
然后你循环你的“日历”，直到你找到最大的完整的true元素序列。重复以找到任何较小的并将它们输出为数组。
希望这对您来说是一个可行的起点，我很想看到有人用 PHP 实现它！
于 2012-07-20T13:55:58.933 回答
0
我不确定你是否做对了。我的意思是像你的第三个例子。array(1, 2, 4, 5, 11, 12)你怎么能确定这些不是 1-2 月、4-5 月和 11-12 月的 3 个序列或 11-2 月和 4-5 月的 2 个序列。是否有任何用户输入可以控制此序列或我正在发生的其他事情？
于 2012-07-20T13:21:56.113 回答