合并相同的ip段算法

Question

$arr = array(
    '1.1.1.1_4.1.1.8',
    '2.2.2.1_5.5.5.5',
    '110.1.1.1_194.2.168.1',
    '192.168.1.1_223.233.223.1',
    '192.165.1.2_199.2.2.1',
    '4.4.4.4_6.6.6.6',
    '8.8.8.1_10.1.1.1',
    '8.1.1.1_9.10.10.10',
    '18.1.1.1_19.2.2.2',
    '9.0.0.1_12.9.9.10',
    );
    

$arr中下划线用来间隔一个ip段的，现在要去合并相同的ip段，得到一个新的数组，不考虑子网掩码，例如，1.1.1.1_192.168.1.1,假设有9.9.9.9或者在这之间的都会合并，最后只保留1.1.1.1_192.168.1.1，算法尽可能效率高一些

怕别人没有听明白：举个例子.
1.1.1.1_3.3.3.3
3.2.2.2_6.6.6.6
那么合并后的结果就是：1.1.1.1_6.6.6.6

假设：
1.1.1.1_3.3.3.3
4.4.4.4_6.6.6.6
那么合并后的结果不变，还是这两个，因为中间的段有间隔

Answer 1

自己写了个，忽略最后结果重复的问题（这个可以在除重下），谁看看能举出不通过的反例或者提出更好的算法

$arr = array(
    '1.1.1.1_4.1.1.8',
    '2.2.2.1_5.5.5.5',
    '110.3.1.1_194.2.168.1',
    '192.168.1.1_223.233.223.1',
    '192.165.1.2_193.2.2.1',
    '4.4.4.4_6.6.6.6',
    '8.8.8.1_10.1.1.1',
    '8.1.1.1_9.10.10.10',
    '18.1.1.1_19.2.2.2',
    '9.0.0.1_12.9.9.10',
    '195.0.0.1_225.0.0.1',
    '225.0.0.2_225.0.0.111',
    '255.0.0.112_255.0.0.220'
    );



function getIp($ip){
    return bindec(decbin(ip2long($ip)));
}

function trans_to_num($arr){
    $ip_num_arr = [];
    foreach ($arr as $ip_segment) {
        list($startIp,$endIp) = explode('_', $ip_segment);
        $ip_num_arr[getIp($startIp)] = getIp($endIp);
    }
    ksort($ip_num_arr);
    return $ip_num_arr;
}



function merge_ip($arr){
    $merge_arr = [];
    foreach ($arr as $key => $value) {
        $merge_arr[]=['start'=>$key,'end'=>$value];
    }
    $finsh_arr = [];
    $tmp = array_shift($merge_arr);
    foreach ($merge_arr as $k=>$ip_arr) {
        if($ip_arr['start']<$tmp['end'] && $ip_arr['end']<$tmp['end']){
            continue;
        }elseif($ip_arr['start']<$tmp['end'] && $ip_arr['end']>$tmp['end']){
            $tmp['end'] = $ip_arr['end'];
        }else{
            $finsh_arr[]=$tmp;
            $tmp['start'] = $tmp['start'];
            if($ip_arr['start']>=$tmp['end']){
                $tmp['start'] = $ip_arr['start'];    
            }
            $tmp['end'] = max([$ip_arr['end'],$tmp['end']]);
        }
    }
    $finsh_arr[] = $tmp;
    return $finsh_arr;
}

$d = trans_to_num($arr);
$m = merge_ip($d);

echo PHP_EOL;
foreach ($m as $key => $value) {
    echo long2ip($value['start']).'---'.long2ip($value['end']).PHP_EOL;
}

Answer 2

没看明白，要合并发的话，最后只可能有一个结果啊，按楼主的举例来说

1.1.1.1_223.233.223.1 肯定合含了所有段啊，
如果是这样的话，比较最首位的最大值和最小值，分别记录一下不就可以了，但这样，无论数组里面有多少ip段，最后只有一个结果啊

既然楼主修改了问题，也大概明白了
提供一个思路，把Ip 转为 int以后就行比较，应该会比较方便。

function ip2int(ip){
      var num = 0;
      ip = ip.split(".");
      num = Number(ip[0]) * 256 * 256 * 256 + Number(ip[1]) * 256 * 256 + Number(ip[2]) * 256 + Number(ip[3]);
      num = num >>> 0;
      return num;
  }

Answer 3

用土办法的话:
ip地址4位，
1.首先分段按第一位分段，第一位作为key值，按key升序。
2.分组里面如果大于两个，就要取出最大和最小，第一位固定比较大小其实很容易。比方说1.2.3.4和1.3.4.5，每位最多是三位数，你可以补齐成12位数字，001002003004和001003004005就可以排序出最大和最小了。
3.第一步经过第二步处理后，数据里面的段，就只有一个和两个这样子的类型，按key顺序遍历，处理就好了