首页 > 代码库 > 189. Rotate Array
189. Rotate Array
<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 14.0px "Helvetica Neue"; color: #323333 }
span.s1 { }
span.s2 { font: 13.0px Menlo; color: #c7254e; background-color: #f9f2f4 }</style>
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.
Solution 1: note that line 6 uses k%size. the time complexity of erase is O(n), so the worst total time could be O(n^2)
1 class Solution { 2 public: 3 void rotate(vector<int>& nums, int k) { 4 int size=nums.size(); 5 int i=0; 6 while (i<size-k%size){ 7 nums.push_back(nums[0]); 8 nums.erase(nums.begin()); 9 i++; 10 } 11 } 12 };
Solution 2:reverse the previous n-k nums and then reverse the later k nums. Finally reverse all. O(n)
<style>p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 14.0px Arial; color: #494949 } p.p2 { margin: 0.0px 0.0px 0.0px 0.0px; font: 14.0px Arial; color: #ff2500 } span.s1 { } span.s2 { color: #ff2500 }</style>1 2 3 4 5 6 7
4321567
4 3 2 1 7 6 5
5 6 7 1 2 3 4
1 class Solution { 2 public: 3 void rotate(vector<int>& nums, int k) { 4 if (nums.empty() || (k %= nums.size()) == 0) return; 5 int n = nums.size(); 6 reverse(nums.begin(), nums.begin() + n - k); 7 reverse(nums.begin() + n - k, nums.end()); 8 reverse(nums.begin(), nums.end()); 9 } 10 };
189. Rotate Array
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。