php - Hackerrank 圆形数组旋转在 php 中未通过 100,000 次旋转测试

Question

我的第一个解决方案，POP -> 依次取消移动每个元素，工作正常，但由于超时而失败。

所以我重构了它，现在它无法通过 100,000 次旋转(具有 500 个元素)测试。

我不知道如何解决这个问题，所以它运行得很快。

有什么想法吗？

<?php
$handle = fopen("php://stdin", "r");

// n = array length
// k = rotations
// q = # of queries in array
list($n, $k, $q,) = explode(' ', trim(fgets($handle)));

// what's our data
$arr = explode(' ', trim(fgets($handle)));

// pull queries
for($i = 0; $i < $q; $i++) {
    $_pos[] = trim(fgets($handle));
}

// NOTE: This is where the test case of 100k rotations on a
//       500 element array fails
// rotate array
$slice = array_slice($arr, -$k, $k);
$arr = array_slice($arr, 0, (count($arr) - $k));
$arr = array_merge($slice, $arr);

// ask the questions
for($i = 0; $i < $q; $i++) {
    echo $arr[$_pos[$i]] . "\n";
}

?>

Answer 1

这是我的解决方案:

//Fetch the input.
$handle = fopen("php://stdin", "r");
fscanf($handle, "%d %d %d", $n, $k, $q);

$inputArray = explode(" ", trim(fgets($handle)));
array_walk($inputArray, 'intval');

//Rotate the array
$totalTimesToRotate = ($k < $n) ? $k : ($k % $n);
if ($totalTimesToRotate > 0) {
    $slicedArray = array_splice($inputArray, -$totalTimesToRotate);
    $inputArray = array_merge($slicedArray, $inputArray);
}

//For all the queries, return the o/p
for ($i = 0; $i < $q; $i++) {
    fscanf($handle, "%d", $m);
    echo $inputArray[$m], "\n";
}

解释: 对于此处 hackerrank 中提到的示例用例: https://www.hackerrank.com/challenges/circular-array-rotation

3 2 3
1 2 3
0
1
2

所以，n(数组项总数) 是 3 k(要执行的总旋转数) 2 q(查询总数)

这一行的目的

$totalTimesToRotate = ($k < $n) ? $k : ($k % $n);

是为了减少总旋转数。 假设，n 为 3，k 为 5

First rotation: [3, 1, 2]
Second rotation: [2, 3, 1]
Third rotation: [1, 2, 3]
Fourth rotation: [3, 1, 2] 
Fifth rotation: [2, 3, 1]

请注意第五轮和第二轮的结果是如何相同的。 当对长度为 n 的数组执行 n 次旋转时，您会得到相同的输出。因此，通过 mod % 操作，我们避免了不必要地迭代的可能性。

array_splice将删除的项目数等于您要执行该操作的次数。 所以你得到 [2, 3] 作为输出并且 inputArray 是 [1] 在下一步中，[array_merge] 将生成 [2, 3, 1]，这是所需的输出。

您的解决方案导致超时的原因是因为您使用了array_slice 两次，而同样的事情可以用 array_splice 完成。