leetcode 189 [数组] 旋转数组

[TOC]

不得不提出还有时间复杂度O(n)的解法,但是第一次刷题没有管,以后还需要留意

题目

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

Given an array, rotate the array to the right by k steps, where k is non-negative.

思路

题目有要求有空间复杂度O(1),需要对是对数组本身操作。
观察最终结果:

5,6,7,1,2,3,4

直觉可以尝试将结果分为两块字符串来处理:

5,6,7 | 1,2,3,4

做数组题时,有一种其他的角度便是从后往前看,那么翻转结果后可以看为:

4,3,2,1 | 7,6,5

即对初始条件进行三次翻转操作即可
1. 翻转[0,length]
2. 翻转[0,length%k-1]
3. 翻转[length%k-1,length]

C++ 实现

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums.begin(),nums.end());
        reverse(nums.begin(),nums.begin()+k);
        reverse(nums.begin()+k,nums.end());
    }
};

时间复杂度:O(2n)

整个数组被翻转两次

空间复杂度:O(1)

发表评论