分享
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
无序的多个范围段,有交集的合并,最后产出有序的无交集的范围段。
如[[24, 41], [58, 75], [79, 89], [62, 80], [5, 10], [20, 30]]
结果就是:[[5, 10], [20, 41],[58, 89]]
$arr = [[24, 41], [58, 75], [79, 89], [62, 80], [5, 10], [20, 30]];
mergeSortArr($arr);
function mergeSortArr($arr){
$arrCount = count($arr);
if ($arrCount <= 1){
return $arr;
}
$tmpArr = array();
foreach ($arr as $k => $v){
$tmpArr[] = array('v'=>$v[0], 'k'=>$k, 'c'=>0);
$tmpArr[] = array('v'=>$v[1], 'k'=>$k, 'c'=>1);
}
qsort($tmpArr, 0, count($tmpArr) - 1);
$ret = array();
$n = count($tmpArr);
$xor = 0;
$tmpItem = array();
for ($i = 0; $i < $n; $i++){
$tmpItem[] = $tmpArr[$i]['v'];
$xor ^= $tmpArr[$i]['k'];
if (1 === ($i % 2) && 0 === $xor){
$ret[] = array($tmpItem[0], $tmpItem[count($tmpItem) - 1]);
$tmpItem = array();
}
}
return $ret;
}
function qsort(&$arr, $st, $end){
if ($st < $end){
$pos = $this->qsortItem($arr, $st, $end);
qsort($arr, $st, $pos-1);
qsort($arr, $pos+1, $end);
}
}
function qsortItem(&$arr, $st, $end){
while ($st < $end){
while($st < $end && $arr[$end]['v'] > $arr[$st]['v']){
$end--;
}
$tmp = $arr[$st]; $arr[$st] = $arr[$end]; $arr[$end] = $tmp;
while($st < $end && $arr[$end]['v'] > $arr[$st]['v']){
$st++;
}
$tmp = $arr[$st]; $arr[$st] = $arr[$end]; $arr[$end] = $tmp;
}
return $st;
}
有疑问加站长微信联系(非本文作者))
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信1504 次点击
上一篇:go分库分表 主从分离例子
下一篇:Golang设计模式之过滤器模式
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传