题目
给你一个数组,将数组中的元素向右轮转 k
个位置,其中 k
是非负数
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出:[5,6,7,1,2,3,4]
思路分析
关键点:旋转
把这个数组比喻成一个圆的直径,当我们翻转180°时,令left为最左边,right为正好落在了最后边。当我们再次翻转180°,又会还原成自己。
所以针对这个数组,当我们进行2次翻转,数组里面元素的排列顺序是不会改变的,而元素的位置取决于旋转对称轴。
所以, 这里旋转的本质就是:l 和 r对调,l - 1 和r - 1对调,直到l <= r
于是,我们可以分2步
①把整个数组旋转
翻转前: nums = [1,2,3,4,5,6,7]
翻转后: nums = [7,6,5,4,3,2,1]
②对数组分段旋转, 以k为分界点
a. 对0 ~ k - 1区间的元素进行翻转 [5,6,7,4,3,2,1]
b. 对k ~ numsSize - 1的元素进行翻转 [5,6,7,1,2,3,4]
代码实现
void reserve(int *nums, int l, int r, int k, int numsSize){ int tmp; while (l < r) { tmp = nums[l]; nums[l] = nums[r]; nums[r] = tmp; l++; r--; } } void rotate(int* nums, int numsSize, int k){ int left = 0; int right = numsSize - 3 + 1; int ret; if ((nums == NULL) || (numsSize < 1)) return 0; k = k % numsSize; // 翻转整个数组 reserve(nums, 0, numsSize - 1, k, numsSize); // 翻转前k个元素 reserve(nums, 0, k - 1, k, numsSize); // 翻转剩余元素 reserve(nums, k, numsSize - 1, k, numsSize);}
号主:一枚机械专业本科生,经历了转行,从外包逆袭到芯片原厂的Linux驱动开发工程师,深入操作系统的世界,贯彻终身学习、终身成长的理念。平时喜欢折腾,寒冬之下,抱团取暖,期待你来一起探讨技术、搞自媒体副业,程序员接单和投资理财。【对了,不定期送闲置开发板、书籍、键盘等等】。
如果你想了解我的转行经验,欢迎找我交流~gongzhong号【哆哆jarvis】
一起不断探索自我、走出迷茫、找到热爱,希望和你成为朋友,一起成长~