LeetCode刷题（8）～旋转数组

题目描述

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

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的 原地 算法。

解答

提交代码_1（暴力解法）

void rotate(vector<int>& nums, int k) {
        int len=nums.size();
        for(int i=0;i<k;++i)
        {
            int temp=nums[len-1];
            for(int j=len-2;j>=0;--j)
            {
                nums[j+1]=nums[j];
            }
            nums[0]=temp;
        }
    }

运行结果（超时）

思路

        每次移动一位，移动k位，则循环k次。

提交代码_2(反转数组)

class Solution {
public:
    void reverse(vector<int> &nums,int start,int end)
    {
        int count=(end-start+1)/2;
        int temp=0;
        for(int i=0;i<count;++i)
        {
            temp=nums[end];
            nums[end]=nums[start];
            nums[start]=temp;
            start++;
            end--;
        }
    }
    void rotate(vector<int>& nums, int k) {
        int len=nums.size();
        k%=len;
        reverse(nums,0,len-1);
      reverse(nums,0,k-1);
      reverse(nums,k,len-1);
    }
};

运行结果

思路

        首先对整个数组进行反转，然后对0～k-1前面的数组反转，再对后面的数组进行反转即可。【易错：当数组个数少于k时，这个比较坑，为了避免这个问题，对k进行重新赋值，k%=len】

提交代码_3【环状替换 难点】

void rotate(vector<int>& nums, int k) {
      int len=nums.size();
      int count=0;
      for(int start=0;count<len;++start)
      {
        int current=start;
        int prv=nums[start];
        do{
            int next=(current+k)%len;
            int temp=nums[next];
            nums[next]=prv;
            current=next;
            prv=temp;
            count++;
        }while (current!=start);
        
      }
    }

运行结果

思路

​​传送门​​

C++完整测试代码

#include <iostream>
#include <vector>
using namespace std;
// 方法一：暴力解法
void rotate_1(vector<int> &nums, int k)
{
  int len = nums.size();
  for (int i = 0; i < k; ++i)
  {
    int temp = nums[len - 1];
    for (int j = len - 2; j >= 0; --j)
    {
      nums[j + 1] = nums[j];
    }
    nums[0] = temp;
  }
}

// 方法二：反转数组
void reverse(vector<int> &nums, int start, int end)
{
  int count = (end - start + 1) / 2;
  int temp = 0;
  for (int i = 0; i < count; ++i)
  {
    temp = nums[end];
    nums[end] = nums[start];
    nums[start] = temp;
    start++;
    end--;
  }
}
void rotate_2(vector<int> &nums, int k)
{
  int len = nums.size();
  k %= len;
  reverse(nums, 0, len - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, len - 1);
}
// 方法三：环转替换
void rotate_3(vector<int> &nums, int k)
{
  int len = nums.size();
  int count = 0;
  for (int start = 0; count < len; ++start)
  {
    int current = start;
    int prv = nums[start];
    do
    {
      int next = (current + k) % len;
      int temp = nums[next];
      nums[next] = prv;
      current = next;
      prv = temp;
      count++;
    } while (current != start);
  }
}
int main()
{
  vector<int> a;
  // 初始化 a=[1,2,3,4,5,6]
  a.push_back(1);
  a.push_back(2);
  a.push_back(3);
  a.push_back(4);
  a.push_back(5);
  a.push_back(6);
  // 使用方法一
  // rotate_1(a,3);

  // 使用方法二
  //  rotate_2(a,3);

  // 使用方法三
  rotate_3(a, 3);

  // 打印结果
  for (int i = 0; i < a.size(); ++i)
    cout << a[i] << " ";

  return 0;
}