189.旋转数组

发表于 | 分类于
字数统计: 418 | 阅读时长 ≈ 1

一、题目描述

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

示例 1:

1
2
3
4
5
6
输入: [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
2
3
4
5
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:

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

二、题解

1.算法描述

  • 暴力法：两个for循环嵌套，每次将数组中的元素向后移动一位
  • 三次翻转数组

2.个人分析

  • 暴力法挺好理解就是超时
  • 三次翻转：
    • 第一次：将整个数组翻转
    • 第二次：将[0,k-1]的数组翻转
    • 第三次：将[k,n-1]的数组翻转

3.代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void reverse(int *nums, int low, int high)
{
    while (low < high)
    {
        int temp;
        temp = nums[low];
        nums[low] = nums[high];
        nums[high] = temp;
        low++;
        high--;
    }
}
void rotate(int *nums, int numsSize, int k)
{
    if (numsSize < 2)
        return;
    k = k % numsSize;
    reverse(nums, 0, numsSize - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, numsSize - 1);
}

三、PS：

暴力法的超时代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//超时了
   void rotate(int *nums, int numsSize, int k)
   {
       if (numsSize < 2)
           return;
       int minK = k % numsSize;
       int i, temp, j;
       for (j = 0; j < minK; j++)
       {
           temp = nums[numsSize - 1];
           for (i = numsSize - 1; i > 0; i--)
           {
               nums[i] = nums[i - 1];
           }
           nums[0] = temp;
       }
   }