如何交换子数组？

Question

如何在没有像这样的辅助数组的情况下重新排列整数子数组（对于随机m）？

example input [1,2,3,4,5,6,7,8,9,10]            
m=3;             
expected output :
[4,5,6,7,8,9,10,1,2,3]

example input : 
[1,2,3,4,5]            
m=4
example output         
[5,1,2,3,4]   
                 
example input :
[1,2,3,4,5,6]        
m=2              
example output
[3,4,5,6,1,2]

我已经尝试创建一个临时数组并且它起作用了，但是它可以提高内存效率吗？

Answer 1

是的，你可以在 O(n) 时间和 O(1) space 内解决这个问题。这涉及反转子数组。

下面以一位为例：

[1,2,3,4,5,6,7,8,9,10]

m = 3

有 2 个指针并交换第一个和最后一个元素，第二个和倒数第二个元素，依此类推。所以，对于上面的例子，我们的数组看起来像：
```
[10,  9,  8,  4,  5,  6,  7,  3,  2,  1]
 ----------                   ---------
      A                           C
              -------------
                    B
```
重要提示： 如果 m 的值大于数组大小的一半，您将自行停止交换。
在上面的场景中，我们成功地将数组分成了 3 个部分，我分别命名为 A、B 和 C.

现在，反转部分C。所以这部分现在想通了。

[10,  9,  8,  4,  5,  6,  7,  1,  2,  3]
 ----------                   
      A                           
              -------------
                    B

反转部分 B 如下所示

[10,  9,  8,  7,  6,  5,  4,  1,  2,  3]
 ----------                   
      A                           
              -------------
                    B

现在，反转整个部分 (B + A)，这是您的最终输出。
```
[4,  5,  6,  7,  8,  9,  10,  1,  2,  3]
```

注意： 有时，B 部分可能不存在。所以在这种情况下你只需反转整个 A 数组（或者你可以添加额外的 if 条件）

片段：

     private static void rotateArray(int[] arr,int m){
        int left = 0,right = arr.length - 1;
        int limit = Math.min(m,arr.length/2);
        while(left < limit){
            swap(arr,left++,right--);
        }

        reverse(arr,arr.length - m,arr.length-1);
        reverse(arr,m,arr.length-m-1);
        reverse(arr,0,arr.length-m-1);
    }

    private static void reverse(int[] arr,int left,int right){
        while(left < right){
           swap(arr,left++,right--);
        }
    }

    private static void swap(int[] arr,int x,int y){
        int temp = arr[x];
        arr[x] = arr[y];
        arr[y] = temp;
    }

演示： https://onlinegdb.com/HklMoZKG4U

Answer 2

很简单，就是将第0个索引处的元素向左移动一个位置，m次后移动到最后一个索引。

程序:

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int input[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int m = 3;
        int temp, i, j;
        for (i = 1; i <= m; i++) { // m times
            temp = input[0];
            for (j = 1; j < input.length; j++) {
                input[j - 1] = input[j];
            }
            input[input.length - 1] = temp;
        }
        System.out.println(Arrays.toString(input));
    }
}

输出：

[4, 5, 6, 7, 8, 9, 10, 1, 2, 3]

Answer 3

题目类似于向左旋转数组... 在阅读解决方案之前尝试应用此... 我在没有使用任何额外 space 的情况下旋转了数组。代码如下..

 #include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,rot,lpos=0;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
         cin>>arr[i];
    cin>>rot;    // number of times to rotate
    int num=0,tmp,ntmp=arr[0],npos,pos=0;
    while(1)
    {
            npos=pos-rot;  // new position of element at position pos
            if(npos<0)
            {
                npos=n-rot+pos;
            }
            tmp=arr[npos];  // saved the element at npos
            arr[npos]=ntmp;
            ntmp=tmp;
            num++;
            if(num==n) // if first position again occours then exit
                break;
            if(npos==lpos)
                {
                    lpos++;
                    pos=lpos;
                    ntmp=arr[pos];
                }
                else
            pos=npos;
    }
    for(int i=0;i<n;i++)
            cout<<arr[i];
    return 0;
}

Answer 4

您可以使用 Arrays.stream(int[],int,int) method two times to get two streams with the specified ranges of the array: near and far, then swap them and concat 返回一个流：

int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int n = 3;

int[] rotated = IntStream
        .concat(Arrays.stream(arr, n, arr.length),
                Arrays.stream(arr, 0, n))
        .toArray();

System.out.println(Arrays.toString(rotated));
// [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]

^{另请参阅：Rotate an elements in an array between a specified range}

如何交换子数组？

How to swap the sub-arrays?

java

arrays

algorithm

rotation

array-algorithms