LeetCode Rotate Array

LeetCode 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.

[show hint]

Related problem: Reverse Words in a String II


本题要把一个数组向右旋转k步,尽量想出3种方法。

首先,无论什么解法,都先判断一下n是否小于2,如果是的话,不管k是多少,都不必旋转了。其次,执行k%=n,因为移动n的倍数位相当于没移动。

暴力解法是每次保留最后一位数字,然后把前n-1个数往后移动一位,重复操作k次。代码如下:

class Solution {
public:
	void rotate(vector<int>& nums, int k) {
		int n = nums.size();
		if (n < 2 || k%n == 0)return;
		k %= n;
		while (k--) {
			int last = nums[n - 1];
			int j = n - 2;
			while (j >= 0) {
				nums[j + 1] = nums[j];
				--j;
			}
			nums[0] = last;
		}
	}
};

本代码提交TLE,过不了最后一个大数据集,因为最坏是O(n^2)复杂度。

稍微高明一点的方法是,先把末尾k位数保存到一个临时数组中,然后一次性把前n-k个数移动到末尾,最后再把临时数组中的数据回帖到原数组开头。完整代码如下:

class Solution {
public:
	void rotate(vector<int>& nums, int k) {
		int n = nums.size();
		if (n < 2 || k%n == 0)return;
		k %= n;
		vector<int> right(nums.begin() + n - k, nums.end());
		int i = n - k - 1, j = n - 1;
		while (i >= 0) nums[j--] = nums[i--];
		i = 0;
		while (i < k) {
			nums[i] = right[i];
			++i;
		}
	}
};

本代码提交AC,用时29MS。

还可以对上述解法稍加变换,即把末尾k位数保存到临时数组right中,然后把原数组的前n-k个数拼接到right的后面,vector的拼接可以用insert。思路和上述算法是一样的。代码如下:

class Solution {
public:
	void rotate(vector<int>& nums, int k) {
		int n = nums.size();
		if (n < 2 || k%n == 0)return;
		k %= n;
		vector<int> right(nums.begin() + n - k, nums.end());
		right.reserve(n);
		right.insert(right.end(), nums.begin(), nums.begin() + n - k);
		nums = right;
	}
};

本代码提交AC,用时19MS。

最后还有一种很巧妙的方法,比如题目中的例子,要对1,2,3,4,5,6,7向右旋转3位,我们可以首先对整个数组逆序一下(reverse),编程7,6,5,4,3,2,1,然后再对前k=3,后n-k=4个数分别逆序,得到5,6,7,1,2,3,4,这不就是最终答案吗,很有意思。数组逆序可以直接用STL中的reverse,其实也可以自己实现,就是收尾元素不断交换swap。这种解法是常数空间复杂度、O(n)时间复杂度的,代码如下:

class Solution {
private:
	void my_reverse(vector<int>::iterator bg, vector<int>::iterator ed) {
		--ed;
		while (bg < ed) {
			swap(*bg, *ed);
			++bg;
			--ed;
		}
	}
public:
	void rotate(vector<int>& nums, int k) {
		int n = nums.size();
		if (n < 2 || k%n == 0)return;
		k %= n;
		my_reverse(nums.begin(), nums.end());
		my_reverse(nums.begin(), nums.begin() + k);
		my_reverse(nums.begin() + k, nums.end());
	}
};

本代码提交AC,用时19MS。

Leave a Reply

Your email address will not be published. Required fields are marked *