Hi！ I am working on this problem rn and the solution shown as given

class CheckRotateArray{
 //Rotates given Array by 1 position
 public static void rotateArray(int[] arr) {

//Store Last Element of Array.
//Start from last and Right Shift the Array by one.
//Store the last element saved to be the first element of array.
int lastElement = arr[arr.length - 1];

for (int i = arr.length - 1; i > 0; i--) {

   arr[i] = arr[i - 1];
 }

  arr[0] = lastElement;
}
 } //end of rotateArray

I am confused about the loop part, since I iterate from the start to the end, not backward

my code be like:

class CheckRotateArray{

public static void rotateArray(int[] arr){
  
int n = arr.length;
for(int i=1; i<n-1; i  ){
   arr[i] =arr[i 1];
}

 arr[0] = arr[n-1];
 return; 
}

}

And of course, mine doesn't work The output is like this:

could somebody explain why I am wrong? And how can I iterate from the head to the end of the array? or why it is better to traverse/iterate backwards? Thanks!!

CodePudding user response：

Java code to solve this challenge:

class Solution {
public void rotate(int[] nums, int k) {
    
    if(nums==null || nums.length<2)
        return;
    
    k%=nums.length;
      
    process(nums,0,nums.length-k-1); 
    process(nums,nums.length-k,nums.length-1);
    process(nums,0,nums.length-1);
    
}

public void process(int[] nums,int i,int j)
{
    int temp=0;
    
    while(i<j)
    {
        temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
        
        i  ;
        j--;
        
    }
}
}

CodePudding user response：

The problem is twofold: to move everything to the right, you should move the element from the left to the right. So, instead of arr[i] = arr[i 1], it should be arr[i 1] = arr[i].

But then, you'd be at the exact problem that iterating backwards solve. I'll use just 3 elements and unroll the loop to make it clear what I mean:

arr = [1, 2, 3];

// unrolled loop: i've 'hard-coded' the loop steps
// to show what happens at every index, just to illustrate
arr[1] = arr[0]; // copy 0 to 1 -> [1, 2, 3] becomes [1, 1, 3]
arr[2] = arr[1]; // copy from 1 to 2 -> [1, 1, 3] becomes [1, 1, 1]
arr[0] = arr[2]; // everything is already 1

If you change the i 1 element, how you'll use it to set i 2?

In the "proposed solution", it's solved by first storing the last element outside the loop (something you didn't mention, so maybe you didn't notice), then iterating backwards to avoid overwriting the element you will still need, and finally, using the last element stored outside the loop.