Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
63 lines (61 sloc) 1.4 KB
/*
* @lc app=leetcode.cn id=189 lang=cpp
*
* [189] 旋转数组
*
* https://leetcode-cn.com/problems/rotate-array/description/
*
* algorithms
* Easy (36.09%)
* Total Accepted: 42.8K
* Total Submissions: 116K
* Testcase Example: '[1,2,3,4,5,6,7]\n3'
*
* 给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
*
* 示例 1:
*
* 输入: [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,-100,3,99] 和 k = 2
* 输出: [3,99,-1,-100]
* 解释:
* 向右旋转 1 步: [99,-1,-100,3]
* 向右旋转 2 步: [3,99,-1,-100]
*
* 说明:
*
*
* 尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
* 要求使用空间复杂度为 O(1) 的原地算法。
*
*
*/
//two pointers reverse
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k %= nums.size();
int mid = nums.size() - k;
//翻转左边数组
int l = 0, r = mid - 1;
while (l < r)
swap(nums[l++], nums[r--]);
//翻转右边数组
l = mid, r = nums.size()-1;
while (l < r)
swap(nums[l++], nums[r--]);
//翻转整个数组
l = 0, r = nums.size() - 1;
while (l < r)
swap(nums[l++], nums[r--]);
}
};
You can’t perform that action at this time.