<leetcode刷题-数组> 【双指针】旋转数组

简介: 【双指针】旋转数组

题目

给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3

输出:[5,6,7,1,2,3,4]

思路分析

关键点:旋转

把这个数组比喻成一个圆的直径,当我们翻转180°时,令left为最左边,right为正好落在了最后边。当我们再次翻转180°,又会还原成自己。

640.png

所以针对这个数组,当我们进行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】

一起不断探索自我、走出迷茫、找到热爱,希望和你成为朋友,一起成长~

相关文章
|
5天前
使用指针访问数组元素
【10月更文挑战第30天】使用指针访问数组元素。
16 3
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
38 0
|
3月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
4天前
使用指针访问数组元素
【10月更文挑战第31天】使用指针访问数组元素。
10 2
|
13天前
|
算法 索引
单链表题+数组题(快慢指针和左右指针)
单链表题+数组题(快慢指针和左右指针)
22 1
|
22天前
|
存储
如何使用指针数组来实现动态二维数组
指针数组可以用来实现动态二维数组。首先,定义一个指向指针的指针变量,并使用 `malloc` 为它分配内存,然后为每个子数组分配内存。通过这种方式,可以灵活地创建和管理不同大小的二维数组。
|
22天前
|
存储
如何通过指针数组来实现二维数组?
介绍了二维数组和指针数组的概念及其区别,详细讲解了如何使用指针数组模拟二维数组,包括定义与分配内存、访问和赋值元素、以及正确释放内存的步骤,适用于需要动态处理二维数据的场景。
|
22天前
|
存储 算法 C语言
C语言:什么是指针数组,它有什么用
指针数组是C语言中一种特殊的数据结构,每个元素都是一个指针。它用于存储多个内存地址,方便对多个变量或数组进行操作,常用于字符串处理、动态内存分配等场景。
|
28天前
魔法指针 之 二级指针 指针数组
魔法指针 之 二级指针 指针数组
16 1
|
1月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
19 4