旋转数组(将数组元素循环右移k次)_已知一个一维数组中存放了10个整数,请将其循环右移k位。

189.旋转数组(将数组元素循环右移k次)

题目：
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

1. 每次只将最后一个元素右移至数组头部位置，重复k%nums.length次即可。

public void rotate(int[] nums, int k) {
      if(nums.length<2) return;
      for(int i=0;i<k;i++){
          int target = nums[nums.length-1];
          for(int j=nums.length-2;j>=0;j--){
           nums[j+1] = nums[j];
       }
       nums[0] = target;
      }
   }
1
2
3
4
5
6
7
8
9
10

2. 使用辅助数组。
可以使用额外的数组来将每个元素放至正确的位置。用 n表示数组的长度，我们遍历原数组，将原数组下标为 i的元素放至新数组下标为(i+k) mod n 的位置，最后将新数组拷贝至原数组即可。

public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> newArr(n);
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        nums.assign(newArr.begin(), newArr.end());
    }
1
2
3
4
5
6
7
8
9

3.数组翻转。

• 当我们将数组的元素向右移动 k次后，尾部 k%n 个元素会移动至数组头部，其余元素向后移动 k%n 个位置。
• 该方法为数组的翻转：我们可以先将所有元素翻转，这样尾部的k%n个元素就被移至数组头部，然后我们再翻转 [0, （k%n）-1] 区间的元素和 [k%n, n-1]区间的元素即能得到最后的答案。
  

 public void rotate(int[] nums, int k) {
       k %= nums.length;
       reverse(nums,0,nums.length-1);
       reverse(nums, 0, k-1);
       reverse(nums,k,nums.length-1);
    }
    public void reverse(int[] nums,int start,int end){
        while(start<end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }  
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2,3来自https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/