Fork me on GitHub

leetcode之189. 旋转数组

发表于 | 分类于
字数统计 500 字 | 阅读时长 2 分钟

题目描述：

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

示例 1:

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

说明:

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

解题思路一：

时间复杂度：$O(n^2)$, 空间复杂度为 :$O(1)$. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int temp;
        
        while(k)
        {
            temp = nums[nums.size() - 1];
            for(int i = nums.size() - 2; i >= 0; i--)
            {
               nums[i + 1] = nums[i]; 
            
               if(i == 0) 
               {
                  nums[i] = temp;
                  k--;
                
               }
            
               if(k == 0) break;
             }
        
        }
        
    }
};

解题思路二：

时间复杂度：$O(n)$, 空间复杂度为 :$O(1)$. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int temp;
        
        if(nums.size() <= 1)  return ;
    
        k = k % nums.size();
            
       for(int i = 0, j = nums.size() - k - 1; i < j; i++, j--)
        {
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            
        }
        
        for(int i = nums.size() - k, j = nums.size() - 1; j > i; i++, j--)
        {
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        
        for(int i = 0, j = nums.size() - 1; j > i; i++, j--)
        {
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }  
        
        
    }
};

解题思路三：

时间复杂度：$O(n)$, 空间复杂度为 :$O(1)$. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        
        if(nums.size() <= 1)  return ;
    
        k = k % nums.size();
            
        swapp(0,nums.size() - k - 1);
        
        swapp(nums.size() - k, nums.size() - 1);

        swapp(0, nums.size() - 1);
    }
    
    void swapp(int i, int j)
    {
           int temp;
            while(i < j)
            {
                temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                
                i++;
                j--;
            }

    }
    
};