LeetCode 热题 100_轮转数组（15_189_中等_C++）(额外数组；翻转)(void函数使用return)

题目描述：

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

输入输出样例：

示例 1：
输入: nums = [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：
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：
1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
0 <= k <= 10⁵

题解：

解题思路：

思路一（额外数组）：
1、我们可以采用额外的数组来暂时存储从后方移动向前方的k个元素，再将前方剩余的元素移动到后方，再将数组暂存的元素放入前方。

2、以nums = [1,2,3,4,5,6,7], k = 3为例
① k=3意味着末尾有三个元素移到前端，且三个元素相对位置不变。
② 我们可以使用一个额外的空间tmp存储末尾移动到前端的元素tmp=[5,6,7]。
③ 则此时nums中的元素可以进行移动nums=[1,2,3,1,2,3,4]。
④ 最后我们将tmp中的元素放在nums的前端 nums=[5,6,7,1,2,3,4]

3、复杂度分析：
① 时间复杂度：O(N)，其中 N 是数组中的元素数量。
② 空间复杂度：O(N)，取决于k%nums.size()的大小，取值0~N-1，所以为O(N)。

思路二（翻转）：
1、先将数组进行翻转，再将两个分数组进行翻转。
例：nums = [1,2,3,4,5,6,7], k = 3。
① 先将nums翻转[7,6,5,4,3,2,1]
②再将前k=3个元素翻转，后续元素也翻转[5,6,7,1,2,3,4] 。

2、复杂度分析
① 时间复杂度：O(N)，其中 N 是数组中的元素数量。因翻转数组两次。
② 空间复杂度：O(1)，我们只需要常数空间存放若干变量。

代码实现（思路一（额外数组））：

#include<iostream>
#include<vector>
using namespace std;

void rotate1(vector<int>& nums, int k) {
	vector<int> tmp; 
	//如果k和数组大小相同则无需移动 
	if (k==nums.size()){
		return ;
	}
	//如果k>数组大小则取余 
	if(k>nums.size()){
		k=k%nums.size();
	}
	//将后端k个元素暂时存储到tmp数组 
	for(int i=nums.size()-k;i<nums.size();i++){
		tmp.emplace_back(nums[i]);
	}
	//将前端剩余的元素移动到后端（从前端的末尾开始） 
	for(int j=nums.size()-k-1;j>=0;j--){
		nums[j+k]=nums[j];
	}
	//将tmp暂存的元素放到前端 
	for(int n=0;n<k;n++){
		nums[n]=tmp[n];
	}
}

int main(){
	vector<int> nums={-1,-100,3,99};
	int k=2;
	rotate1(nums,k);
	for (const auto &num:nums){
		cout<<num<<" "; 
	}
	return 0;
}

代码实现（思路二（翻转））：

#include<iostream>
#include<vector>
using namespace std;
//翻转功能
void reverse(vector<int>& nums,int left,int right){
	while(left<right){
		swap(nums[left],nums[right]);
		++left;
		--right;
	}
} 

void rotate2(vector<int>& nums, int k){
	if (k==nums.size()){
		return ;
	}
	if(k>nums.size()){
		k=k%nums.size();
	}
	//翻转整个nums 
	reverse(nums,0,nums.size()-1);
	//翻转前k个元素 
	reverse(nums,0,k-1);
	//翻转后边剩下的元素 
	reverse(nums,k,nums.size()-1);
}

int main(){
	vector<int> nums={-1,-100,3,99};
	int k=2;
	rotate2(nums,k);
	for (const auto &num:nums){
		cout<<num<<" "; 
	}
	return 0;
}

部分代码解读

void函数使用return

//void 函数可以使用 return; 来结束函数，但不能返回任何值
void fun(){
	if(条件){
		return ;
	}
}

LeetCode 热题 100_轮转数组(15_189)原题链接

欢迎大家和我沟通交流(✿◠‿◠)