Leetcode 189 Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

数组移位,额外要求只能使用O(1) 的空间复杂度。

本质等于最后k个需要移到前面,将最后k个和其余部分先全部逆置,再将整个数组逆置就行了,画个图就能证明出来。

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 18 4Sum

    Given an array S of n integers, are there elements a, b, c, and d in S such tha...

    triplebee
  • Leetcode 27 Remove Element

    Given an array and a value, remove all instances of that value in place and ret...

    triplebee
  • Leetcode 15 3Sum + 有趣的小BUG

    Given an array S of n integers, are there elements a, b, c in S such that a + b...

    triplebee
  • 哈希表:解决了两数之和,那么能解决三数之和么?

    给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三...

    代码随想录
  • LeetCode 215. 数组中的第K个最大元素(快速排序)

    在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

    Michael阿明
  • Python3刷题系列(三)

    中文版:https://leetcode-cn.com/problems/sqrtx/

    用户5473628
  • 剑指Offer LeetCode 面试题57. 和为s的两个数字

    输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

    TrueDei
  • 移动零

    一份执着✘
  • 漫画:经典鹅厂面试题(4sum - nSum)

    第18题:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + ...

    程序员小浩
  • 双指针法:一样的道理,能解决四数之和

    题意:给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c ...

    代码随想录

扫码关注云+社区

领取腾讯云代金券