我正在尝试仅使用单个一维数组将数组循环左移 n 个位置。我可以在两个数组中做到这一点，但我还没有弄清楚如何使用一个来做到这一点。请提出你的建议
问问题
25376 次
15 回答
24
实际上有一个聪明的算法。我们将用A来表示数组，N表示数组大小，并n表示要移动的位置数。移位后，您希望i-th元素移动到该((i + n) mod N)-th位置，因此我们可以通过以下映射定义新位置：
f(j) := (j + n) mod N (j = 0,...,N - 1)
该算法背后的总体思路是这样的：我们不想移动元素超过必要的范围，所以理想情况下，我们希望在第一次尝试时简单地将每个元素放置在正确（移动）的位置。假设我们从 position 的元素开始i。我们要做的是将 position 的元素移动i到 position f(i)，但是我们会覆盖那个位置的元素，所以我们需要先将元素保存在 position f(i)，然后再执行移位。一旦我们移动了第一个元素，我们需要选择另一个元素来移动。由于我们想节省空间，显而易见的候选者是我们刚刚保存的元素（位于 position 的元素f(i)）。像以前一样，我们将元素保存在位置f(f(i))然后将我们保存的元素复制到该位置。我们不断重复这个过程（通过位置i, f(i), f(f(i)), f(f(f(i))), ...），直到我们到达一个我们已经移动的元素（我们保证会这样做，因为有有限多个位置）。如果我们通过了所有元素，那么我们就完成了，如果没有，那么我们选择另一个元素（还没有移动），比如说在 position j，然后重复这个过程（通过j, f(j), f(f(j)), f(f(f(j))), ...）。而已。但在我们可以实现这样的算法之前，甚至在我们决定这是否确实是一个好的算法之前，我们需要回答几个问题：
假设我们遍历 position
i, f(i), f(f(i)), ...。我们如何判断我们到达了一个已经转移的位置？我们需要保存我们通过的每个位置吗？如果我们这样做，那么这意味着我们需要保存一个大小为 N 的数组（以覆盖所有位置），并且我们还需要在每次移动元素时执行查找。这将使算法非常低效。幸运的是，这不是必需的，因为序列i, f(i), f(f(i)), ...必须在 position 处环绕自身i，所以我们只需要等到到达那个位置。我们可以如下证明这个断言：假设我们遇到的第一个重复元素不是i。那么我们必须有 2 个不同的元素，它们在移动时会到达相同的位置 - 矛盾。假设我们完成了
i, f(i), f(f(i)), ...，但仍有一些元素保持未移动（我们可以通过计算移动了多少元素来判断）。我们现在如何找到j包含这样一个元素的位置？而且，一旦我们完成了第二次迭代（通过j, f(j), f(f(j)), ...），我们如何找到k具有未移位元素的第三个位置？等等.. 这也可能表明我们需要保存一个数组来说明使用过的\未使用过的元素，并在每次需要查找未使用的元素时执行查找。但是，我们可以再次放松，因为正如我们很快将展示的，所有起始位置（我们用i和表示）都是相邻的。这意味着，如果我们从 position 开始，我们接下来将 select ，然后jkii + 1i + 2，等等……</p>序列
i, f(i), f(f(i)), ...和（j, f(j), f(f(j)), ...哪里不同）可能包含共同的元素吗？如果他们这样做，则意味着该算法是无用的，因为它可能会移动相同的元素两次 - 导致它最终处于错误的位置。那么答案（当然）是它们不能包含共同的元素。我们将说明原因。ij
让我们表示d := gcd(N, n)。对于每一个整数：i = 0,...,d - 1我们定义以下集合：
S(i) := { kd + i | k = 0,...,N/d - 1}
很容易看出这些集合S(0),...,S(d - 1)一起覆盖了集合{0,...,N - 1}。我们还观察到，当将集合中的元素除以 时S(i)，d我们会得到余数i，而将不同集合中的元素除以S(j)会d留下不同的余数 ( j)。因此，没有两个集合包含一个共同的元素。有了这个，我们已经确定集合S(0),...,S(d - 1)形成了一个分区{0,...,N - 1}
现在，对于每个i = 0,...,d - 1，我们将集合定义T(i)为i, f(i), f(f(i)), ...。根据定义f我们可以写成T(i)：
T(i) = {(kn + i) mod N | k is an integer}
我们观察到如果x是 中的一个元素T(i)，那么我们可以写一些k：
x = (kn + i) mod N = (k(n/d)d + i) mod N
让我们表示z := k(n/d) mod N/d，然后乘以d，我们有：
kn mod N = zd
因此：
x = (kn + i) mod N = zd + i
因此，x也在S(i). 同样，如果我们从中取一些y，S(i)我们会观察到一些k：
y = kd + i
由于gcd(n/d, N/d) = 1存在q这样的q(n/d) mod N/d = 1（模逆），因此我们可以写（乘以kd）：
kd = kqn mod N
因此：
y = kd + i = ((kq)n + i) mod N
因此，y也在T(i). 我们得出结论T(i) = S(i)。从这个事实我们可以很容易地展示我们之前的断言。首先，因为集合形成了{0,...,N - 1}第三个断言的一个分区（没有两个序列包含一个共同的元素）是满足的。其次，通过集合的定义，S(i)我们可以将任何一组d相邻元素放入其中，{0,...N - 1}并且每个元素都将放置在不同的集合中。这满足第二个断言。
这意味着我们可以0, d, 2d, ..., (N/d - 1)d通过简单地将 position 的元素替换为 positionn mod N的元素，将position 的元素替换为0position2n mod N的元素n mod N，依此类推……直到我们返回到 position 的元素0（我们保证会发生）。这是一个伪代码示例：
temp <- A[0]
j <- N - (n mod N)
while j != 0 do
A[(j + n) mod N] <- A[j];
j <- (j - n) mod N
A[n mod N] <- temp;
这涵盖了整个集合S(0)。为了覆盖其余的集合，即S(1), … ,S(d-1)，我们将简单地迭代每个集合，就像我们对第一个集合所做的那样：
for i <- 0 to d - 1
temp <- A[i]
j <- N - ((n - i) mod N)
while j != i do
A[(j + n) mod N] <- A[j];
j <- (j - n) mod N
A[(i + n) mod N] <- temp;
请注意，虽然我们有两个嵌套循环，但每个元素只移动一次，并且我们使用O(1)空间。Java中的一个实现示例：
public static int gcd(int a, int b) {
while(b != 0) {
int c = a;
a = b;
b = c % a;
}
return a;
}
public static void shift_array(int[] A, int n) {
int N = A.length;
n %= N;
if(n < 0)
n = N + n;
int d = gcd(N, n);
for(int i = 0; i < d; i++) {
int temp = A[i];
for(int j = i - n + N; j != i; j = (j - n + N) % N)
A[(j + n) % N] = A[j];
A[i + n] = temp;
}
}
于 2013-08-09T20:19:46.993 回答
2
我会一次将其移动 1 个元素，使用单个临时变量来保存元素，同时将元素移动 1 个位置。然后我会重复这个n时间来实现n转变。
public static void main( String[] args ) {
int[] array = {1,2,3,4,5,6,7,8};
leftShift( array, 3);
System.out.println( Arrays.toString( array));
}
public static void leftShift(int[] array, int n) {
for (int shift = 0; shift < n; shift++) {
int first = array[0];
System.arraycopy( array, 1, array, 0, array.length - 1 );
array[array.length - 1] = first;
}
}
输出：
[4, 5, 6, 7, 8, 1, 2, 3]
不是太低效，因为System.arraycopy()它是高度优化的。
于 2012-08-09T23:58:24.690 回答
2
这是一个非常简单的算法，在 O(n)
算法中有 O(1) 空间
- 将数组从 0 反转到 n (numberOfPositions) 个位置
- 将数组从 n+1 反转为数组长度 - 1 个位置
- 将整个数组从 0 反转为 length - 1 个位置
public class ArrayRotator {
private final int[] target;
private final int length;
public ArrayRotator(int[] seed) {
this.target = seed;
this.length = seed.length;
}
public void rotateInline(int numberOfPositions) {
reverse(0, numberOfPositions);
reverse(numberOfPositions + 1, length-1);
reverse(0, length-1);
}
private void reverse(int start, int end) {
for (int i = start; i <= (start + end)/2; i++) {
swap(i, start + end - i);
}
}
private void swap(int first, int second) {
int temp = this.target[second];
this.target[second] = this.target[first];
this.target[first] = temp;
}
}
例如，假设数组 is[1,2,3,4]和nis2
在step one之后，您将[2,1,3,4]
在Step 2之后结束，您将[2,1,4,3]
在Step 3之后结束，您将结束[3,4,1,2]
于 2016-01-29T11:12:47.170 回答
1
我相信System.arraycopy实际上只会从一个数组中获取所有数据，然后将其放入另一个相同长度的数组中。
无论如何，思考这个问题是一项非常有趣的任务。我现在唯一能想到的解决方案就是一个一个地把它拉屎。如果不使用另一个数组，它看起来像这样：
for(int i = 0; i < shift;i++)
{
tmp = array[0];
for(int j = 0;j<array.length-1;j++)
array[j]=array[j+1];
array[array.length-1]=tmp;
}
对于超过 30 个项目的数组，使用它会更有效：
for (int i = 0; i < shift; i++) {
tmp = array[0];
System.arraycopy( array, 1, array, 0, array.length - 1 );
array[array.length - 1] = tmp;
}
但是对于接近数组大小的大数组和大移位以及短数组和小移位，这种方法赢得了比赛：
int[] array2 = new int[shift];
for (int i = 0; i < shift; i++)
{
array2[i] = array[i];
}
System.arraycopy(array, shift, array, 0, array.length - shift);
for (int i = array.length - shift; i < array.length; i++)
{
array[i] = array2[shift + i - array.length];
}
我已经用一些数组大小和移位测试了以下是结果
int[] array = new int[100000];
int shift = 99999;
以纳秒为单位：第一种方法：5663109208 第二种方法：4047735536 第三种方法：6085690 所以你真的应该使用第三种方法。希望有帮助
于 2012-08-10T01:30:03.563 回答
1
另一种选择是包装您自己的结构，其中包括数组和虚拟零的索引。
于 2012-08-10T00:19:51.967 回答
1
您可以通过迭代和复制来移动数据，这将是 O(n)。另一种方法是创建一个List包装您的数组并将其公开为循环移位的实现。这样做的好处是，当get执行或迭代时，实际的移位是延迟完成的。
于 2012-08-09T23:12:18.040 回答
1
Java 8 版本：
public class Sample {
public static void main(String[] args) {
int[] answer = solution(new int[] {1,2,3,4}, 2);
Arrays.stream(answer).forEach(System.out::print);
}
public static int[] solution(int[] A, int K) {
List<Integer> numbers =
IntStream.of(A).boxed().collect(Collectors.toList());
Collections.rotate(numbers, K);
return numbers.stream().mapToInt(n -> n).toArray();
}
}
于 2017-04-27T05:59:21.757 回答
0
for (int i = 0; i < n; i++)
array[array.length - n + i] = array[i];
for (int i = 0; i < array.length - n; i++)
array[i] = array[i + n];
于 2012-08-09T23:49:34.320 回答
0
查看此 github 链接：
圆形ShiftToLeftInPlace
于 2014-01-16T23:54:11.003 回答
0
我知道这是一个旧帖子，但我没有在任何地方看到这个帖子，所以：
d 是我们想要向左移动的位置。
int[] array = {1,2,3,4,5,6,7,8};
int length = array.length;
int d = 3;
int[] ans = new int[length];
for (int i = 0; i < length; i++){
ans[i] = array[(i + d)%length];
}
System.out.println(Arrays.toString(ans));
它将输出： [4, 5, 6, 7, 8, 1, 2, 3]
你可以在这里看到代码：http: //tpcg.io/8cS6GIKI
编辑：没关系......我无法阅读。我刚刚看到 OP 只要求 1 个数组。我的错。我会留下我的答案，以防万一它可以帮助某人。
于 2021-01-06T23:54:13.350 回答
0
下面我实现了一个示例解决方案，将数组左移或右移 n 个元素。
class RotateArrayByN {
public void leftRotate(int arr[], int d, int n)
{
for (int i = 0; i < d; i++)
leftRotatebyOne(arr, n);
}
public void rightRotate(int[] arr,int d, int n){
for(int i=0;i<d;i++)
rightRotatebyOne(arr,n);
}
public void leftRotatebyOne(int arr[], int n)
{
int i, temp;
temp = arr[0];
for (i = 0; i < n - 1; i++)
arr[i] = arr[i + 1];
arr[i] = temp;
}
public void rightRotatebyOne(int[] arr,int n){
int temp=arr[n-1];
for (int i=n-1;i>0;i--) {
arr[i] = arr[i - 1];
}
arr[0]=temp;
}
public void printArray(int arr[], int n)
{
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String[] args)
{
RotateArrayByN rotate = new RotateArrayByN();
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
System.out.println("Left Rotate");
rotate.leftRotate(arr, 2, 7);
rotate.printArray(arr, 7);
//System.out.println("Right Rotate");
//rotate.rightRotate(arr,2,7);
// rotate.printArray(arr,7);
}
}
我已经注释掉了正确的转变。
于 2020-02-09T03:51:47.537 回答
0
也许是一个旧帖子..但这是我的解决方案（A显然是数组和K位置数）。
public int[] solution(int[] A, int K){
int[] result = new int[A.length];
for (int i = 0; i<A.length; i++){
result[(i+K)%A.length] = A[i];
}
return result;
}
于 2016-05-24T20:57:37.303 回答
0
我知道这是一篇旧文章，但是这是 O(n) 中的最佳解决方案：每个元素只移动一次，不需要额外的空间。它与@SomeStrangeUser 提出的解决方案非常相似，但不需要 gcd 计算。
public static void shiftArray(int[] A, int k) {
if (A.length == 0) {
return;
}
k = k % A.length;
k = (k + A.length) % A.length; // ensure k is positive
if (k == 0) {
return;
}
int i = 0, i0 = 0;
int x = A[0];
for (int u = 0; u < A.length; u++) { // count number of shifted elements
int j = (i - k + A.length) % A.length; // ensure modulo is positive
if (j == i0) { // end of a (sub-)cycle, advance to next one
A[i] = x;
x = A[i = ++i0];
} else {
A[i] = A[j];
i = j;
}
}
}
于 2021-12-21T14:41:06.060 回答
-1
这个怎么样？
// Left shift the array in O(n) with O(1) space.
public static void leftShift(int[] array, int n) {
int temp;
int len = array.length;
for (int i = 0; i < n; i++) {
temp = array[len - n + i];
array[len - n + i] = array[i];
array[i] = array[n + i];
array[n + i] = temp;
}
}
于 2014-11-29T06:53:15.470 回答
-1
import java.util.Scanner;
public class ArrayMoveByGivenSize {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] A = new int[] {100,200,300,400,500,600};
//movement = 2
//output {500,600,100,200,300,400}
System.out.println("Please enter the movement size");
int s;
Scanner sc = new Scanner(System.in);
s= sc.nextInt();
System.out.println(s);
int[] X = new int[A.length];
for (int i=0;i<A.length;i++)
{
if((i+s)<A.length)
{
X[i+s]=A[i];
}
else
{
X[(i+s) - A.length]=A[i] ;
}
}
for(int i =0;i<X.length ; i++)
System.out.println(X[i]);
}
}
于 2021-06-08T04:36:48.043 回答