0

如何在没有这样的辅助数组的情况下重新排列整数子数组（对于随机数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]

我已经尝试创建一个临时数组并且它可以工作，但它可以做得更高内存效率。

4

4 回答 4

3

O(n)是的，你可以在时间和O(1)空间上解决这个问题。这涉及反转子阵列。

我们以下面的一个为例：

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

米 = 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

于 2020-02-25T10:27:29.263 回答
2

这个问题类似于向左旋转数组......在阅读解决方案之前尝试应用这个......我已经旋转了数组而不使用任何额外的空间......代码如下...... 

 #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;
}
于 2020-02-25T13:55:24.430 回答
0

它就像在将剩余元素向左移动一个位置之后将第 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]
于 2020-02-25T10:47:29.020 回答
0

您可以使用Arrays.stream(int[],int,int)方法两次来获取具有指定数组范围的两个流：near和far，然后将它们交换并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]

另请参阅：在指定范围之间旋转数组中的元素

于 2021-02-15T09:11:43.010 回答