So rufen Sie schnell den entsprechenden Wert ab

Ein PHP-Index-Array. Die Werte im Array sind Ganzzahlen von 1 bis 100 (nicht wiederholend), und die Werte können intermittierend sein, das heißt, es kann 7 und 9 geben, aber keine 8. Und die Reihenfolge ist gestört, das heißt, sie ist nicht von 1 bis 100 geordnet

Angenommen, $a=50, wie kann man schnell ==$a oder die beiden Werte herausfinden, die $a am nächsten kommen?

Übrigens müssen die Werte im Array nicht unbedingt gleich $a sein

Antwortinhalt:

Ein PHP-Index-Array. Die Werte im Array sind Ganzzahlen von 1 bis 100 (nicht wiederholend), und die Werte können intermittierend sein, das heißt, es kann 7 und 9 geben, aber keine 8. Und die Reihenfolge ist gestört, das heißt, sie ist nicht von 1 bis 100 geordnet

Angenommen, $a=50, wie kann man schnell ==$a oder die beiden Werte herausfinden, die $a am nächsten kommen?

Übrigens müssen die Werte im Array nicht unbedingt gleich $a sein

1. array_search – Suchen Sie nach dem angegebenen Wert im Array und geben Sie bei Erfolg den entsprechenden Schlüsselnamen zurück

2. erhält den Schlüsselnamen, $arr[$key-1], $arr[$key+1] kann

sein

Das obige ist sehr einfach, aber wenn Sie die Nummer nicht finden, suchen Sie die nächste. Die Reihenfolge des ursprünglichen Arrays ist durcheinander, sodass die oberen und unteren natürlich nicht unbedingt die nächsten sind , zwei Punkte Die Suche ist auch eine Idee. Meine Idee ist, zuerst die Fasssortierung zu verwenden (der schnellste Weg, positive ganze Zahlen zu sortieren, den ich derzeit kenne)

<code>//这个是要求的数组
$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自增，同时值是排序的数组，然后再结合楼上的写法，便可求出。
</code>

Ich weiß nicht, wie effizient das ist

<code>$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) && ($arr[$key+1] > $target)) {
            echo "左边：{$value} <br/>";
            echo "右边：{$arr[$key+1]}";
            exit;
        }
    }
}</code>

Statische Abfrage ohne Änderung

• Sortieren (aufsteigende Reihenfolge), Komplexität nlogn (eine Sortierung)

• Dann schnelle Positionierung um zwei Punkte, Komplexitätsprotokoll (eine Abfrage)

// 在有序数组$arr中得到大于等于$val的第一个下标
// 如果想要获得离$val最近的值，通过返回值判断
// 如果大于最大的值，返回数组的长度
function binary_search($arr, $val){
    $n = count($arr) - 1;
    $ans = $n + 1;
    $l = 0; $r = $n; 
    while($l <= $r){
        $mid = ($l + $r) >> 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("%d\n", binary_search($arr, $search_num));

Dynamische Abfrage nur mit Add-Vorgang, ohne die Reihenfolge zu ändern

1-100 hat 100 Zahlen und sein Wert ist auch 1-100. Wenn Sie nach dem Index der Position von 69 fragen, können Sie 69 als Mittelpunkt und eine binäre Suche verwenden, um den Index des Punktes in der Nähe zu finden Wenn eine bestimmte Position vorhanden ist, markieren Sie sie als 1, andernfalls markieren Sie sie als 0. Nehmen Sie dann 69 als Mittelpunkt, halbieren Sie sie nach links, um das längste Intervall zu ermitteln und die Summe ist 0, und halbieren Sie sie nach rechts, um das zu ermitteln Das längste Intervall und die Summe sind 0. Sie können Bäume verwenden, um die Intervallsumme schnell zu ermitteln. Wie bei einem Array ist die Komplexität der Aktualisierungsabfrage logn und die Komplexität des Addierens von Zahlen ist logn.
Anforderungen und Zwecke:

• Das Baumarray speichert die Intervall-Flag-Summe (ob der Wert eines bestimmten Intervalls angezeigt wird) und die Aktualisierungs- und Abfragekomplexität ist logn

• Suchen Sie den Wert, der einem bestimmten Wert als Mittelpunkt am nächsten kommt, und geben Sie dann seinen Index, die binäre Suche und das Komplexitätsprotokoll zurück

• Tauschen Sie Platz gegen Zeit und speichern Sie die Wert->Indexzuordnung.

• Sie können Zahlen am Ende des Arrays hinzufügen und müssen sie nicht der Reihe nach hinzufügen

Der folgende Code löst die folgenden Probleme

Angenommen, es gibt ein Array [5,9,3,8,7,10,12]
Fragen Sie nach der Koordinate, die 12 am nächsten liegt, geben Sie 6 zurück
Fragen Sie nach der Koordinate, die 2 am nächsten liegt, Rückgabe 2
Fügen Sie eine eindeutige Zahl 15 hinzu
Fügen Sie eine eindeutige Zahl 18 hinzu
Fügen Sie eine eindeutige Zahl 16 hinzu
Fügen Sie eine eindeutige Zahl 13 hinzu
Fragen Sie nach den Koordinaten, die 13 am nächsten kommen, und geben Sie 10 zurück
fragt nach den Koordinaten, die 17 am nächsten liegen, und gibt 9 zurück

// 树状数组初始化长度为106，赋空值为0
$arr_bit = array();
for($i = 0;$i <= 105;$i ++){
    $arr_bit[$i] = 0;
}

// 查询1-$x之间的和
function query($x){
    global $arr_bit;
    $sum = 0;
    while($x > 0){
        $sum += $arr_bit[$x];
        $x -= $x & -$x;
    }
    return $sum;
}

// 更新第$x位的标志
function add($x, $val){
    global $arr_bit;
    while($x <= 105){
        $arr_bit[$x] += $val;
        $x += $x & -$x; 
    }
}

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

// 查找离某值最近的下标
// 先查找左边 然后再找右边，若不存在，返回-1
function find_val_pos($val){
    if($val < 1 || $val > 100){
        return -1;
    }
    global $arr_tmp;
    $n = count($arr);
    $l = 1; $r = $val; $ans_l = -1;
    // 得到$val左边最靠近的
    while($l <= $r){
        $mid = ($l + $r) >> 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 <= $r){
        $mid = ($l + $r) >> 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 < 1 || $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("%d\n",find_val_pos(12)); // 结果为6
// 查询2最近的坐标
printf("%d\n",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("%d\n",find_val_pos(13)); // 结果为10

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

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

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

Dynamische Abfrage mit Add- und Löschvorgängen (größere Zahlen)

Sie müssen einen zusätzlichen Intervallwert beibehalten, der vom Index belegt wird, und dann einen ausgeglichenen Binärbaum festlegen, Komplexitätsprotokolle abfragen, Komplexitätsprotokolle hinzufügen und löschen.