java - 如何交换子数组？

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)空间。这涉及反转子数组。

我们以下面的例子为例:

[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