1

初始数组：2 23 34 27 89 14 26 30 60

k = 3

从索引 i = 1 开始，我们必须移动 k 个元素，以便它们出现在数组中的元素 26 之后（即在 givenIndex = 6 之后）。

最终数组： 2 89 14 26 23 34 27 30 60

我们不允许使用额外的空间。

我的做法：

count = 0;   
while(count < k)  
{  
  count++;  
  temp = arr[i];  
  shift all elements from (i+1) to givenIndex to their immediate left position;  
  arr[givenIndex] = temp;  
}

第一次迭代：
temp = 23
将所有元素从 [i+1](即 index=2) 移动到 givenIndex(即 index=6) 移动后一个向左的
数组：2 34 27 89 14 26 26 30 60
arr[givenIndex] =
应用此操作后的临时数组：2 34 27 89 14 26 23 30 60

第二次迭代后的类似
数组：2 27 89 14 26 23 34 30 60
第三次迭代后的数组：2 89 14 26 23 34 27 30 60

最坏情况复杂度 O(n*k) 其中 n 是第一个。数组中的元素。

我们可以解决 O(n) 中的问题吗

4

3 回答 3

1

这种旋转可以使用reverse()辅助函数在线性时间内完成。假设reverse(x, y)反转array[x]..array[y]到位。

reverse(1, 3); // 27 34 23 .. .. ..
reverse(4, 6); // .. .. .. 26 14 89
reverse(1, 6); // 89 14 26 23 34 27

编写线性时间reverse很简单，甚至可能在您最喜欢的语言库中可用（例如，C++ 包含std::rotate和std::reverse）。

于 2012-08-07T07:25:09.353 回答
0

这个问题非常惊人，
请在此处查看您要求的答案。如果您正在寻找一种使用 JAVA 旋转阵列列表的方法，这里有一个完整的解决方案。
public static void rotate(List list, int distance)

只需旋转您的集合（ArrayList 或 LinkedList ...）
它的参数是 a list（在您的情况下arraylist）和 a distance（在您的情况下k）。你看到相似之处了吗？简单地使用这个。

于 2012-08-07T07:44:16.253 回答
0

据我从您的代码（和示例）中可以看出，我认为您正试图将块放在块[i,i+k-1]之后[i+k,givenIndex]

如果是这种情况，@Blastfurnace 的建议确实会导致 O(n) 中的一种解决方案并且没有额外的空间：

只需这样做：

reverse(i,givenIndex)
reverse(i,givenIndex-k)
reverse(givenIndex-k+1,givenIndex)

你有你想要的:)

于 2012-08-07T07:39:49.190 回答