我的第一个解决方案是POP ->依次unshift每个元素，工作正常，但由于超时而失败。
所以我重构了它，现在它失败了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";
}
?>
我的解决方案是:
//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 (total array items) = 3k (total rotations to be performed) 2q ( total queries)
这一行的目的
$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]作为输出，而输入数组是[1]在下一步中，[array_merge]将产生[2, 3, 1]，这是期望的输出。
你的解决方案导致超时的原因是你使用了两次 array_slice ，而同样的可以用 array_splice 。