对两个数组合并,并按值排序

Question

昨天收到个面试题
写一个php函数function merge（$a , $b）合并两数组并排序返回例如：$a =array（12，23,31,37,55）；$b=array（16,23,34）；返回组数array（12,16,23,31,34,37,55） 补充说明：两数组已排序，返回数组要求排序  设计要求：时间复杂度为线性阶，不要使用php的合并和排序函数小弟惭愧连时间复杂度是什么东西都不清楚
我自己费了好多脑细胞写出来个：/*
遍历数组，如果符合条件则另写入结果中。并且从原数组中销毁
*/
$a = array(12, 23, 31, 37, 55);
$b = array(16, 23, 34);
function merge($a, $b)
{
    $x = array();
    // 数组单元数多的在最外围循环，防止$b未完全比较便结束了
    if(count($a)<count($b)) {
       $c = $a;
       $a = $b;
       $b = $c;
    }
    foreach($a as &$n)
    {
       foreach($b as $key=>$m)
       {
            if($n> $m) {
               $x[] = $m;
               unset($b[$key]);
            }
            if($n === $m)
               unset($n);          
       }
       if(!is_null($n))
           $x[] = $n;
    }
   
    return $x;
}$result = merge($b, $a);
var_dump($result);我在Google上找到的感觉比我这个还晦涩，而且首页全是同一篇文章...
请问如何按他这个要求来写，也就是时间复杂度为线性阶？ 或者大伙有别的思路请贴出来

Answer 1

我猜时间复杂度为线性阶 应该是随着数组值的增加，时间复杂度线性增长吧<?php
$a = array(12,23,31,37,55);
$b = array(16,23,34);function merge($a,$b){
$count = count($a);
foreach($b as $v) $a[]=$v;
for($i=$count; $i<count($a);$i++){
$tmp=$a[$i];
$j=$i-1;
while($a[$j] > $tmp){
$a[$j+1] = $a[$j];
$a[$j] = $tmp;
$j--;
}
}
return array_unique($a);
}
print_r(merge($a,$b));
结果倒是出来了，就是不知道符合要求不

Answer 2

考虑到“两数组已排序”，所以也只是选择性粘贴了
时间复杂度 O(n)
function merge($a, $b) {
  $alen = count($a);
  $blen = count($b);
  $ai = $bi = 0;
  $res = array();
  $len = $alen + $blen;
  while($ai<$alen || $bi<$blen) {
    if($a[$ai] == $b[$bi]) {
      $res[] = $a[$ai];
      $ai++;
      $bi++;
    }elseif($a[$ai] < $b[$bi]) {
      if($ai < $alen) { 
        $res[] = $a[$ai];
        $ai++;
      }else {
        $res[] = $b[$bi];
        $bi++;
      }
    }else {
      if($bi < $blen) { 
        $res[] = $b[$bi];
        $bi++;
      }else {
        $res[] = $a[$ai];
        $ai++;
      }
    }
  }
  return $res;
}$a = array(12, 23, 31, 37, 55);
$b = array(16, 23, 34);print_r(merge($a, $b));Array
(
    [0] => 12
    [1] => 16
    [2] => 23
    [3] => 31
    [4] => 34
    [5] => 37
    [6] => 55
)

Answer 3

升序数组，若值唯一，可保留原始下标，否则以$a为准虽然套了循环，但复杂度符合要求的$a = array(12, 23, "c" => 31, 37, 55);
$b = array(11, 18, "bb" => 23, 34, "t" => 44);function merge($a, $b, $flag = FALSE)
{
$count = sizeof($b);
$latest = NULL; $res = array();
foreach($a AS $k => $v)
{
while($count)
{
$val = current($b);
$key = key($b);
if($val < $v)
{
if($latest != $val)
{
$latest = $val;
if($flag && !isset($res[$key]))
{
$res[$key] = $val;
}
else
{
$res[] = $val;
}
}
next($b);
--$count;
continue;
}
break;
}
if($latest != $v)
{
$latest = $v;
if($flag && !isset($res[$k]))
{
$res[$k] = $v;
}
else
{
$res[] = $v;
}
}
}
return $res;
}print_r(merge($a, $b, TRUE));
Array
(
    [0] => 11
    [1] => 12
    [2] => 18
    [3] => 23
    [c] => 31
    [4] => 34
    [5] => 37
    [t] => 44
    [6] => 55
)

Answer 4

#3有些代码多余，并且不够严格，需加以修改……hoho~~~~~

Answer 5

考虑key就麻烦了,问题就变得不清晰，比如
$a        = array(12, 23, "c" => 31, 37, 55);
$b        = array(11, 18, "2" => 23, 34, "t" => 44);//key为数字型

Answer 6

应该说如果考虑key,$a,$b有同key的情况会有问题。

Answer 7

分好多,function merge($a, $b){
$len_a = count($a);
$len_b = count($b);
if ($len_b > $len_a){ 
list($a,$b) = array($b,$a);
}

for ($i = 0; $i < count($a); $i++){
if (empty($b)) break;
$v_a = $a[$i];
$v_b = $b[0];
if ($v_a > $v_b){
array_shift($b);
array_splice($a, $i, 0, $v_b);
}
elseif($v_a == $v_b){
array_shift($b);
}
}
return $a;
}