数据结构算法题】轮转数组(顺序表篇)"/>
【Leetcode数据结构算法题】轮转数组(顺序表篇)
题目内容:
给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。
leetcode题目链接(点击即可跳转)
思路分析
看完题目后,我们首先要做的就是理解题目的含义,也就是审题。从不同维度,不同角度的去设问题并主动回答这些问题。题目中出现了一个我们比较陌生的词语“轮转”,可能我们一下子无法理解这个词是啥子玩意儿。这个时候就可以借助题目中的示例来帮助理解。比如说示例1:
用通俗的话来说就是,向右轮转1步,就是将最后一个元素放到第一个位置,其余元素位置向右移动一个位置。类似于所有元素向右滑动一个位置,只不过最后一个元素向右滑动的时候需要回到第一个位置。
理解了“轮转”的含义后,为了更好的理解题目的要求和隐藏含义,我们需要从以下几个角度进行自我设问:
(1)题目中给的数组有告诉我们数组的长度能否为0?
(2)向右轮转k次的k的实际取值如何,能不能为0?能不能超过数组本身的长度?
关于(1)(2)这两个问题,我们可以看题目的提示部分:
根据提示的内容我们可以清楚的知道,数组的长度至少为1,不能为0。这就解决了问题(1)。另外k的取值范围是0到10^5,虽然没有直接表明k与数组长度之间的关系,但是我们可以猜测,k的大小可以超过数组的长度。也就是说k可以等于0,可以超过数组本身的长度(可以一直向右转啊转),这就解决了问题(2)。这两个问题想清楚后,就可以进行相应的算法分析和设计了。
方法一:k次轮转法
这个方法其实可以通过题目给的示例直接想到。
为了简化问题,我们可以让k先为1,这样就是向右轮转一步。
如果k=2,那么先向右轮转一步,再向右轮转一步。
如果k=3…(套娃套娃再套娃)
另外,当k的大小超过数组的长度时,比如数组长度为5,k=6,这时候向右进行k次轮转,相当于前面5次轮转白做了,只进行了最后1次轮转,因为轮转6次和轮转1次的效果是一样的。所以实际的轮转效果应该为 k=k%(数组的长度)。(这里的轮转效果就是相当于轮转多少次…我随便创造的词方便理解…看不懂也没关系…)
算法图解
函数接口实现
void rotate(int* nums, int numsSize, int k){//求出实际轮转效果k = k % numsSize;
更多推荐
【Leetcode数据结构算法题】轮转数组(顺序表篇)
发布评论