首页 > 其他分享 >力扣-189. 轮转数组

力扣-189. 轮转数组

时间:2024-04-24 22:58:34浏览次数:29  
标签:遍历 轮转 nums int 力扣 start 数组 189

1.题目

题目地址(189. 轮转数组 - 力扣(LeetCode))

https://leetcode.cn/problems/rotate-array/

题目描述

给定一个整数数组 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 <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

 

进阶:

  • 尽可能想出更多的解决方案,至少有 三种 不同的方法可以解决这个问题。
  • 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

2.题解

2.1 新数组存储(空间换时间)

思路

使用一个新数组存储移动k次后的数组状况, 注意索引对应关系即可
最后使用assign函数更新原数组nums即可

代码

class Solution{
public:
	void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        vector<int> arr(n);
        for(int i = 0; i < n; i++){
            arr[(i + k) % n] = nums[i];
        }
        nums.assign(arr.begin(), arr.end());
    }
};

2.2 环状替换

思路

我们之所以不直接将nums[(i+k)%n]替换为nums[i], 是因为这么操作就会使我们丢失关于nums[(i+k)%n]的数据,导致错误;
那么如果我们每次在替换之前用一个临时变量temp存储nums[(i+k)%n]的数据呢? 那我们就可以从第一个数据开始, 向后替换直到再次回到第一个数据
但是这时不一定遍历完了整个数组, 我们必须知道结束条件----目前已经遍历了多少个数,如果已完成(等于数组个数)就结束;反之向后推进一个数,再次展开循环.

由于最终回到了起点,故该过程恰好走了整数数量的圈,所以假设我们总共遍历了a次数组, 数组长度为n, 遍历了b个元素, 每个元素之间的差值为 k.
我们有 an=bk,即 an一定为 n,k 的公倍数(b暂时未知,所以不纳入讨论)
又因为我们要求第一次回到起点时便结束这次遍历,所以a尽可能的小(a可能是最小圈数的任意倍数,但是我们只需要最小倍数即可,无需重复跑圈)
故 an 就是 n,k 的最小公倍数 lcm(n,k), b 就为 lcm(n,k)/k

这说明单次遍历会访问到 lcm(n,k)/k 个元素。为了访问到所有的元素,我们需要进行遍历的次数为

如上, a刚好为n,k的最大公约数,所以我们设置一个外循环规定遍历圈数(也就是第一次起始点和第一次结束时起始点和后面一个被遍历过元素之间所有未被遍历的点(作为循环起始点再次开始循环))

代码

class Solution{
public:
	void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        int count = gcd(n, k);  // 一次循环有等式 (an = bk = lcd(n,k) [要求a最小]), 该次循环遍历 b = lcd(n,k) / k 个元素, 那么遍历完n个元素, 需要循环 n / b = nk / (lcd(n,k)) = gcd(n,k)次       
        for(int start = 0; start < count; start++){
            int current = start , preVal = nums[start]; // 记录当前元素位置 和 前一个元素的值(避免被后面的元素值覆盖)
            do{
                int next = (current + k) %  n; // 记录下一个元素位置

                // 可以简化为 swap(preVal, nums[next]);
                int temp = nums[next];
                nums[next] = preVal;
                preVal = temp;

                current = next;
            }while(current != start); // 这里不能使用next,因为其是循环内部元素
        }
    }
};

2.3 翻转数组(镜像)

思路

这里进行了一个优化k %= nums.size(); // 由于每数组长度次数的移动后,恢复为原数组,所以先减少移动次数到一个数组大小内
原理: 任何一个数组翻转两次后和原数组相同
对于[1,2,3,4,5,6,7], k = 3
1.我们首先进行翻转(镜像) [7,6,5,4,3,2,1]
2.我们将从后端移动至首部的部分看做一个镜像数组(步骤1进行了镜像),所以再次翻转得到实际数组
3.同理,后面部分也看做一个镜像数组,再次翻转得到实际数组

代码

  • 语言支持:C++

C++ Code:


class Solution{
public:
	void rotate(vector<int>& nums, int k) {
        k %= nums.size();
		reverse(nums,0,nums.size()-1);
		reverse(nums,0,k-1);
		reverse(nums,k, nums.size()-1);
    }
    
    void reverse(vector<int>& nums,int start, int end){
    	while (start < end){
    		swap(nums[start++],nums[end--]); 
		}
	}
};

复杂度分析

令 n 为数组长度。

  • 时间复杂度:\(O(n)\)
  • 空间复杂度:\(O(1)\)

标签:遍历,轮转,nums,int,力扣,start,数组,189
From: https://www.cnblogs.com/trmbh12/p/18154163

相关文章

  • 力扣-414. 第三大的数
    1.题目题目地址(414.第三大的数-力扣(LeetCode))https://leetcode.cn/problems/third-maximum-number/题目描述给你一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。 示例1:输入:[3,2,1]输出:1解释:第三大的数是1。示例2:输入:[1,2]输出:2......
  • 力扣-495. 提莫攻击
    1.题目题目地址(495.提莫攻击-力扣(LeetCode))https://leetcode.cn/problems/teemo-attacking/题目描述在《英雄联盟》的世界中,有一个叫“提莫”的英雄。他的攻击可以让敌方英雄艾希(编者注:寒冰射手)进入中毒状态。当提莫攻击艾希,艾希的中毒状态正好持续 duration秒。正......
  • 力扣-665. 非递减数列
    1.题目题目地址(665.非递减数列-力扣(LeetCode))https://leetcode.cn/problems/non-decreasing-array/题目描述给你一个长度为 n 的整数数组 nums ,请你判断在最多改变 1个元素的情况下,该数组能否变成一个非递减数列。我们是这样定义一个非递减数列的: 对于数组中任......
  • 【每周例题】力扣 C++ 分割字符串
    分割字符串题目 题目分析1.先确定用容器存储,容器的存储结构如下图所示: 2.这个题目的话,第一反应应该是用到动态规划,下面是动态规划的模板:res=[]ans=[]defbacktrack(未探索区域,res,path):if未探索区域满足结束条件:res.add(ans)#深度拷贝......
  • 【每周例题】力扣 C++ 最小和分割
    最小和分割题目 题目分析1.num1 和 num2 中所有数字出现的次数之和等于 num 中所有数字出现的次数。即,num1与num2是从num中提取出来的,且不会重复提取同一个数字,且提取的顺序并不需要按照num的数字顺序2.返回 num1 和 num2 可以得到的和的最小值。要想得到最小值,需......
  • 高通将支持 Meta Llama 3 在骁龙终端运行;特斯拉中国全系车型降价 1.4 万元丨 RTE 开发
       开发者朋友们大家好: 这里是「RTE开发者日报」,每天和大家一起看新闻、聊八卦。我们的社区编辑团队会整理分享RTE(RealTimeEngagement)领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有看点的会议」,但内容仅代表编辑的个人观点......
  • 力扣周赛394之别样DP + 别样Dijkstra
    别样DP题目链接https://leetcode.cn/problems/minimum-number-of-operations-to-satisfy-conditions/description/题目大意题目思路需要考虑m列每一列填什么的情况,因为最终每一列都是一样的考虑暴力,每一列都可以变成0-9有\(10^m\)次种情况,这必然是不可行的我们从前往......
  • 2024-04-17:用go语言,欢迎各位勇者莅临力扣城,本次的挑战游戏名为「力扣泡泡龙」。 游戏
    2024-04-17:用go语言,欢迎各位勇者莅临力扣城,本次的挑战游戏名为「力扣泡泡龙」。游戏的起点是一颗形状如二叉树的泡泡树,其中每个节点的值代表该泡泡的分值。勇者们有一次机会可以击破一个节点泡泡,但需要满足以下规则:被击破的节点泡泡最多只能有一个子节点泡泡。如果被击破的节点......
  • 力扣经典150题第十六题:接雨水
    目录力扣经典150题第十六题:接雨水1.题目描述2.问题分析3.解题思路4.代码实现5.时间复杂度分析6.应用和扩展7.总结8.参考资料力扣经典150题第十六题:接雨水1.题目描述给定n个非负整数表示每个宽度为1的柱子的高度图,计算按此排列的柱子,下雨之后能接多少......
  • 力扣经典150题第十五题:分发糖果
    目录力扣经典150题第十五题:分发糖果1.题目描述2.问题分析3.解题思路4.代码实现5.时间复杂度分析6.应用和扩展7.总结8.参考资料力扣经典150题第十五题:分发糖果1.题目描述n个孩子站成一排。给你一个整数数组ratings表示每个孩子的评分。你需要按照以下......