• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

如何快速取出所对应的值

PHP admin 12个月前 (06-08) 7次浏览 未收录 0个评论
文章目录[隐藏]

一个php的索引数组,数组里面的值为从1到100之间的整数(不重复),并且数值可能是断续,也就是可能有就7,9但是没有8。并且顺序是打乱的,也就是,不是从1排到100这样的

现在假设$a=50, 怎样最快的取出==$a或者是跟$a最相邻的两个数值呢?

对了其中数组中的值不一定有等于$a的

回复内容:

一个php的索引数组,数组里面的值为从1到100之间的整数(不重复),并且数值可能是断续,也就是可能有就7,9但是没有8。并且顺序是打乱的,也就是,不是从1排到100这样的

现在假设$a=50, 怎样最快的取出==$a或者是跟$a最相邻的两个数值呢?

对了其中数组中的值不一定有等于$a的

楼上的已经非常简单了,不过需要是如果没有找到这个数,就找最接近的,而原数组顺序是打乱的,所以上下两个并不一定就是最接近的,当然,二分查找也是一种思路,我提供一下自己用算法的思路,我的想法是先用木桶排序(我目前所了解的在正整数中的排序的最快方式)

//这个是要求的数组
$arr = [1,2,3...];

//填充一个1-100范围的数组
$search_arr = array_fill(0 , 99 , 0);

//遍历数组
foreach($search_arr as $k=>$v){
    if(in_array($k , $arr)){
        ++ $v;
    }
}

//此时search_arr数组里面值是1的就是要找的,同时已经排序好了
foreach($search_arr as $k=>$v){
    if($v >= 1){
        $new_arr[] = $k;
    }
}

//此时的new_arr就是一个键从0自增,同时值是排序的数组,然后再结合楼上的写法,便可求出。

不知道这样效率怎么样

$arr = range(1, 100); // 要求的数组
$target = 10; // 目标值
shuffle($arr); // 打乱顺序

$val_key = array_search($target, $arr);
// 测试 $target 不存在的情况去掉以下注释
// array_splice($arr, $val_key, 1);
// $val_key = '';
if ($val_key) {
    echo "这个值是:{$arr[$val_key]}";
} else {
    sort($arr);
    foreach ($arr as $key => $value) {
        if (($value  $target)) {
            echo "左边:{$value} 
"; echo "右边:{$arr[$key+1]}"; exit; } } }

不带修改的静态查询

// 在有序数组$arr中得到大于等于$val的第一个下标
// 如果想要获得离$val最近的值,通过返回值判断
// 如果大于最大的值,返回数组的长度
function binary_search($arr, $val){
    $n = count($arr) - 1;
    $ans = $n + 1;
    $l = 0; $r = $n; 
    while($l > 1;
        if($arr[$mid] >= $val){
            $ans = $mid;
            $r = $mid -1;
        }
        else $l = $mid + 1;
    }
    return $ans;
}

$arr = [1,5,9,3,8,7,10,12];
sort($arr);
foreach($arr as $key => $val){
    printf("%d ", $val);
}
printf("n");

$search_num = 6;

printf("%dn", binary_search($arr, $search_num));

仅带添加操作的动态查询,不改变顺序

1-100有100个数,且其值也为1-100,若询问69所在位置下标,可以以69为中心,二分查找到它附近的点的下标,若某个位置存在数,则标为1,否则标为0,那么以69为中心,往左边二分找最长的区间和为0,往右边二分找最长的区间和为0,快速求区间和可以用了树状数组,更新查询复杂度为logn,添加数的复杂度为logn。
要求和目的:

以下代码解决以下问题

// 树状数组初始化长度为106,赋空值为0
$arr_bit = array();
for($i = 0;$i  0){
        $sum += $arr_bit[$x];
        $x -= $x & -$x;
    }
    return $sum;
}

// 更新第$x位的标志
function add($x, $val){
    global $arr_bit;
    while($x  $val){
    $arr_tmp[$val] = $key;
    printf("%d ",$val);
    add($val, 1);
}
printf("n");

// 查找离某值最近的下标
// 先查找左边 然后再找右边,若不存在,返回-1
function find_val_pos($val){
    if($val  100){
        return -1;
    }
    global $arr_tmp;
    $n = count($arr);
    $l = 1; $r = $val; $ans_l = -1;
    // 得到$val左边最靠近的
    while($l > 1;
        // 获得$val到$mid的标志区间和
        $mid_val = query($val) - query($mid - 1);
        // 若标志区间和大于1,记录答案,l往右移继续查
        if($mid_val >= 1){
            $ans_l = $mid;
            $l = $mid + 1;
        }
        else $r = $mid - 1;
    }
    $l = $val; $r = 101; $ans_r = -1;
    // 得到$val右边最靠近的
    while($l > 1;
        // 获得$mid到$val的标志区间和
        $mid_val = query($mid) - query($val - 1);
        if($mid_val >= 1){
            $ans_r = $mid;
            $r = $mid - 1;
        }
        else $l = $mid + 1;
    }
    if($ans_l == -1) return $arr_tmp[$ans_r];
    elseif ($ans_r == -1) return $arr_tmp[$ans_l];
    else {
        if($val - $ans_l > $ans_r - $val)
            return $arr_tmp[$ans_r];
        else
            return $arr_tmp[$ans_l];
    }
}

function add_num($val){
    if($val  100) return false;
    global $arr_tmp;
    if(isset($arr_tmp[$val])){
        return false;
    }
    else {
        global $arr;
        $arr_n = count($arr);
        $arr_tmp[$val] = $arr_n;
        $arr[$arr_n] = $val;
        add($val, 1);
        return true;
    }
}

// 查询12最近的坐标
printf("%dn",find_val_pos(12)); // 结果为6
// 查询2最近的坐标
printf("%dn",find_val_pos(2));  // 结果为2

add_num(15); // 15位于7
add_num(18); // 18位于8
add_num(16); // 16位于9
add_num(13); // 13位于10

// 查询13最近的坐标
printf("%dn",find_val_pos(13)); // 结果为10

// 查询17最近的坐标
printf("%dn",find_val_pos(17)); // 结果为9

// 查询15最近的坐标
printf("%dn",find_val_pos(15)); // 结果为7

printf("hhn");
// 查询100最近的坐标
printf("%dn",find_val_pos(100)); // 结果为8,因为第8个位置是18,是最大的数

带添加删除操作(较大数)的动态查询

需要额外维护一个下标占用的区间值,然后套一个平衡二叉树,查询复杂度logn,添加删除复杂度logn。


39MO , 版权所有丨如未注明 , 均为原创丨转载请注明原文链接:如何快速取出所对应的值
喜欢 (0)
[1353713598@qq.com]
分享 (0)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址