未排序的数组 - 从下一个更高的值获取索引 |复杂度 O(n)，PHP

Question

我搜索了一个 PHP 算法 复杂度 O(n)。我有一个非整数数组，我希望每个元素都有比这个值最近的索引号，如果不存在则为 -1。
注意：每个值都是唯一的。

示例:

$arr = [7, 3, 5, 4];
$result = [-1, 3, 0, 2];

解释：

7 没有更大的值 => -1
3 下一个更大的值 4 => 3
5 下一个更大的值 7 => 0
4 下一个更大的值 5 => 2

解决方案工作正常但它的 O(n²):

function follows ($arr, $index) {
    $filter = array_filter($arr, function($el) use ($arr, $index) { return $el > $arr[$index]; });
    if (count($filter)===0)
        return -1;
    else
        return array_search(min($filter), $arr);
}

$res = [];
for ($i=0; $i<count($arr); $i++) {
    $res[] = follows($arr,$i);
}
var_dump($res); // => [-1, 3, 0, 2]

搜索复杂度为 O(n) 的解决方案

我应该使用 asort（例如：[3, 4, 5, 7]），因此值已排序，我可以在那里获得下一个元素的原始索引。

这是它的部分想法：

$arr = [ 7, 3, 5, 4];
asort($arr);
for($i=0; $i<count($arr); $i++) {
    echo 'For: ' . $i . ': ' . $arr[$i].'<br>';
}

echo "<br>";

foreach ($arr as $key => $val) {
    echo 'ForEach; ' . $key . ': ' . $val .'<br>';
}

echo '<br><br>' . $arr[2];

在使用 asort 排序后，索引与您在 for-loop 中看到的相同，但在 forEach-loop 中，它们被重新排序，但索引仍然相同。
思路：从for循环中取索引得到forEach循环对应的索引加1得到original-index
示例： 我数组中的索引 1 的值为 3，在 for 循环中索引仍然为 1，但在 forEach 循环中索引为 0。到达下一个元素（索引 1 ) 值为 4 的原始索引为 3.

最后一步很简单。任何人都可以在没有找到的情况下帮助从 for 的索引到 forEach 的索引中获取丢失的 link 吗？

Answer 1

我将数组迭代 3 次（array_flip，for，for）并对它进行 1 次排序（ksort）。我不知道如何计算复杂性...也许，将循环计算为 O(N)，将 ksort 计算为 O(N*log(N))。所以最终的复杂度是O(N*log(N))。我不能把它变小:)

$arr = [7, 3, 5, 4];

$flip = array_flip($arr); // prepare for sort
ksort($flip); // sort

// put results into place
$keys = array_keys($flip);
for ($i = 0; $i < count($flip) - 1; $i++) {
    $flip[$keys[$i]] = $flip[$keys[$i + 1]];
}
$flip[$keys[count($keys) - 1]] = -1;

// finalize results
$result = [];
for ($i = 0; $i < count($arr); $i++) {
    array_push($result, $flip[$arr[$i]]);
}

print_r($result);

要测试的外部 link：click

Answer 2

这是一个不翻转数组的版本，因此可以处理任何类型的数组数据。它使用单个循环和 asort，O(n*log(n)) 也是如此。数据排序后，使用key函数循环确定下一个较大值的key；当循环完成时，最终的“下一个”值设置为 -1（因为没有更大的值）。此时输出具有正确的 key/value 对，但不是数字顺序（这可能足以满足您的需要）：

$arr = [7, 3, 5, 4];
asort($arr);
$temp = [];
$count = 1;
$key = key($arr);
while (next($arr) !== false) {
    $temp[$key] = key($arr);
    $key = key($arr);
    $count++;
}
$temp[$key] = -1;
print_r($temp);

输出：

Array
(
    [1] => 3
    [3] => 2
    [2] => 0
    [0] => -1
)

如果您需要对键进行排序（例如，如果您希望在使用 foreach 循环时条目按顺序排列），您可以使用另一个循环，利用 $count 上面代码中生成的变量，将值复制到一个新的有序数组中：

$result = [];
for ($i = 0; $i < $count; $i++) {
    $result[] = $temp[$i];
}
print_r($result);

输出：

Array
(
    [0] => -1
    [1] => 3
    [2] => 0
    [3] => 2
)

如果您不需要这个，您可以从第一个代码块中删除 $count 的计算。

Demo on 3v4l.org

未排序的数组 - 从下一个更高的值获取索引 |复杂度 O(n)，PHP

Unsorted array - Getting index from next higher value | Complexity O(n), PHP

php

arrays

sorting

complexity-theory

search

解决方案工作正常但它的 O(n²):

搜索复杂度为 O(n) 的解决方案