C语言超详细讲解轮转数组

目录
  • 题目描述
  • 实例
  • 解题思路
    • 1. 先整体逆转
    • 2.逆转子数组[0, k - 1]
    • 3.逆转子数组[k, numsSize - 1]
  • 易错点
  • 代码

题目描述

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。OJ链接

实例

1.实例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.实例2

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

解题思路

为了使算法空间复杂度为O(1),原地旋转，所以不能额外创建数组。

以实例1为例子。使用三次逆转法，让数组旋转k次

  • 先整体逆转 变为（7,6,5,4,3,2,1）
  • 逆转子数组[0, k - 1] 变为（5,6,7,4,3,2,1）
  • 逆转子数组[k, numsSize - 1] 变为(5,6,7,1,2,3,4)

1. 先整体逆转

设置两个指针变量分别指向头部和尾部。当 begin<end 时，交换两个位置上的值。绿色的数字为交换的位置。

2.逆转子数组[0, k - 1]

3.逆转子数组[k, numsSize - 1]

此处不赘述、同上面两个步骤的思路。这样就完成了对数组的轮转。

易错点

假如需要轮转的个数k大于数组numsSize的长度呢？

假如k为10，那么本题的结果是什么呢？

假如右旋10个数，那么先旋7个后将又回到了原来的样子。 然后再旋3个的话那么将和本题的旋3个一模一样。

  • 本题的精髓就是题目，叫做轮转数组。果然天道好轮回。轮转7次又回到了起点。轮转14次，21次…，只要七的倍数都回返回原地。
  • 所以在题目中要加入是否为k的倍数的判断代码
	if (k > numsSize)
	{
		k %= numsSize;
	}

代码

此代码带主函数。LeetCode题目中是接口类型的不带主函数。因为要轮转三次。所以把while循环写成一个函数，方便复用。

 LeetCode189. 轮转数组
#include<stdio.h>

void rotate1(int* begin, int* end)
{
	while (begin < end)
	{
		int t = 0;
		t = *begin;
		*begin = *end;
		*end = t;
		++begin;
		--end;
	}
}
void rotate(int* nums, int numsSize, int k)
{
	//假如右旋10个数，先旋7个后又回到了原来的样子。然后再旋3次的话和本题再旋3次一模一样。
	if (k > numsSize)
	{
		k %= numsSize;
	}
	int* begin = nums;
	int* end = nums + numsSize - 1;
	rotate1(begin, end);
	rotate1(begin, begin+k-1);
	rotate1(begin + k, end);

}
int main()
{
	int nums[] = { 1,2,3,4,5,6,7 };
	int sz = sizeof(nums) / sizeof(nums[0]);
	rotate(nums, sz, 3);

	for (int i = 0; i < sz; i++)
	{
		printf("%d ", nums[i]);
	}
	return 0;
}

到此这篇关于C语言超详细讲解轮转数组的文章就介绍到这了,更多相关C语言 轮转数组内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 从头学习C语言之二维数组

    从头学习C语言之二维数组

    目录 二维数组: 语法: 二维数组存放方式: 二维数组的访问: 二维数组的初始化: 示例: 总结 二维数组: 引入一个想法: 一个变量:相当于一个点. 一维数组(也就是数组):点汇聚成为一条直线. 二维数组:直线汇聚成一个平面. 三维数组:平面汇聚成立体图形. 语法: 类型 数组名[常量表达式][常量表达式] int a[6][6];//6*6,6行6列 char b[4][5];//4*5,4行5列 double c[6][3];//6*3,6行3列 二维数组存放方式: 二维数组的访问: 数组

  • C语言 柔性数组的使用详解

    目录 一.柔性数组的特点 二.柔性数组的使用 1.如何使用柔性数组 2.不用柔性数组的话有什么代替 三.柔性数组的优势 1.方便内存释放 2.提高访问速度 一.柔性数组的特点 struct S { int x; int a[]; }; int main() { printf("%d", sizeof(S)); } 这段代码的输出是什么? 我们打印结构体S所占空间的大小,这个a[]占多少字节呢? 输出结果是4,可一个int类型的x就是4了,a[]去哪了?好奇怪哦. 原来,这是一种柔性数组

  • C语言数组全面总结梳理

    C语言数组全面总结梳理

    目录 一,一维数组 1.创建和初始化 2.使用下标访问 3.在内存中的存储 二,二维数组 1.创建和初始化 2.使用下标访问 3.在内存中的存储 三,越界问题 数组(array)是由一系列类型相同的元素构成. 一般形式: 类型     数组名  [常量表达式] 一,一维数组 1.创建和初始化 创建一堆相同元素的集合,以整型为例: //创建大小为8的整型数组 int arr1[8]; // []里面应放常量,因此若: int num=8; //则有: arr2[num]; num为变量,创建失败

  • C语言 指针数组进阶详解

    C语言 指针数组进阶详解

    目录 指针与数组中的sizeof与strlen sizeof strlen 数组名 1.一维数组 整型数组 字符数组 指针数组 2.二维数组 指针笔试题 笔试题1 笔试题2 笔试题3 笔试题4 笔试题5 前言:指针与数组的知识往往让我们无法给自己定位,似乎是懂了,但真的碰上了又一言难尽.接下来有一些关于指针与数组的知识和例题讲解,来看看你对指针和数组到底有多了解吧! 指针与数组中的sizeof与strlen sizeof sizeof值关注占用空间的大小,单位是字节,不关注元素的类型,是一个操作

  • c语言循环加数组实现汉诺塔问题

    目录 简介 递归的汉诺塔解法(c语言) 循环实现汉诺塔问题(c语言) 简介 汉诺塔问题是学数据结构与算法的时候会遇到的问题,相信来看本文的读者应该都对汉诺塔问题有基本的了解,理论上所有的递归都可以改成循环,常规的做法是借助堆栈,但是我一想好像用循环加数组也可以实现,于是就有了本文,实现声明,本文最后出来的算法效率不高的,比直接用递归实现还要差很多,追求算法效率的同学就不用看这个了.题目:假设有3个柱子,分别为A.B.C,A柱子上有数量为n个的空心圆盘,从上到下序号分别为1...n,要求把A柱子中

  • C语言中的柔性数组你真的了解吗

    C语言中的柔性数组你真的了解吗

    目录 柔性数组概念: 特点: 与指针动态开辟的比较 指针动态开辟 柔性数组 指针动态开辟的缺点 总结 柔性数组概念: 柔性数组就是一种特殊的数组 它也是结构体最后一个成员 也就是说,它存在结构体最后一个成员的位置上 特点: 1.柔性数组在结构体的大小是未知的,在sizeof中不计算其大小 #include<stdio.h> struct S { int n ; int arr[0];//或者int arr[]; }; main() { printf("The size of the

  • C语言数组和指针,内存之间的关系

    C语言数组和指针,内存之间的关系

    首先论证一维数组和一级指针之前的关系,我们常常使用一级指针指针的方式访问一维数组,只有对内存的理解到位才能理解它们直接的关系. 1.数组名是数组的首地址 2.对数组名取地址得到的还是数组的首地址 3.数组的访问方式其实就是首地址+偏移的寻址访问 我们在程序中会定义很多变量,有基本类型和自定义类型在进行开发的时候我对内存的访问访问就是通过变量名赋值的方式读写内存但是如果你看到的直接变量的符号名你将不可能理解内存.每一种类型都有字节宽度,char 1字节 short 2字节 int 字节float

  • C语言超详细讲解轮转数组

    C语言超详细讲解轮转数组

    目录 题目描述 实例 解题思路 1. 先整体逆转 2.逆转子数组[0, k - 1] 3.逆转子数组[k, numsSize - 1] 易错点 代码 题目描述 给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数.OJ链接 实例 1.实例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

  • C语言 超详细讲解链接器

    C语言 超详细讲解链接器

    目录 1 什么是链接器 2 声明与定义 3 命名冲突 3.1 命名冲突 3.2 static修饰符 4 形参.实参.返回值 5 检查外部类型 6 头文件 1 什么是链接器 典型的链接器把由编译器或汇编器生成的若干个目标模块,整合成一个被称为载入模块或可执行文件的实体–该实体能够被操作系统直接执行. 链接器通常把目标模块看成是由一组外部对象组成的.每个外部对象代表着机器内存中的某个部分,并通过一个外部名称来识别.因此,==程序中的每个函数和每个外部变量,如果没有被声明为static,就都是一个外部

  • C语言 超详细讲解库函数

    目录 1 返回整数的getchar函数 2 更新顺序文件 3 缓冲输出与内存分配 4 库函数 练习 1 返回整数的getchar函数 代码: #include<stdio.h> int main() { char c; while((c = getchar())!=EOF)//getchar函数的返回值为整型 putchar(c); return 0; } 上述代码有三种可能: 某些合法的输入字符在被"截断"后使得c的取值与EOF相同,程序将在复制的中途停止. c根本不可能

  • C语言 超详细讲解算法的时间复杂度和空间复杂度

    C语言 超详细讲解算法的时间复杂度和空间复杂度

    目录 1.前言 1.1 什么是数据结构? 1.2 什么是算法? 2.算法效率 2.1 如何衡量一个算法的好坏 2.2 算法的复杂度 2.3 复杂度在校招中的考察 3.时间复杂度 3.1 时间复杂度的概念 3.2 大O的渐进表示法 3.3 常见时间复杂度计算举例 4.空间复杂度 5. 常见复杂度对比 1.前言 1.1 什么是数据结构? 数据结构(Data Structure)是计算机存储.组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合. 1.2 什么是算法? 算法(Algorit

  • C语言超详细讲解字符串相乘

    C语言超详细讲解字符串相乘

    目录 前言 一. 分析思路 二.使用步骤 1.代码如下 2.memset函数 三.总结 前言 我们已经知道,正常的两位整形数据通过*相乘,C语言中int为4字节,32bit(字节),其机器码第一位为符号位,余下31位表示数字,表示范围:-2^31(-2147483648)~2^31-1(2147483647),但超过了这个范围我们该如何做呢? 提示:将数字以字符串的形式进行操作 一. 分析思路 示例: 我们把每一个数都看成是一个字符串,每一个元素为十进制数字所对应的字 符,由于是后面的元素先进行

  • C语言超详细讲解排序算法上篇

    C语言超详细讲解排序算法上篇

    目录 1.直接插入排序 2.希尔排序(缩小增量排序) 3.直接选择排序 4.堆排序 进入正式内容之前,我们先了解下初阶常见的排序分类 :我们今天讲前四个! 1.直接插入排序 基本思想:当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排 序码与array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移! 直接插入排序的特性总结: 1. 元素集

  • C语言超详细讲解栈与队列实现实例

    C语言超详细讲解栈与队列实现实例

    目录 1.思考-1 2.栈基本操作的实现 2.1 初始化栈 2.2 入栈 2.3 出栈 2.4 获取栈顶数据 2.5 获取栈中有效元素个数 2.6 判断栈是否为空 2.7 销毁栈 3.测试 3.1测试 3.2测试结果 4.思考-2 5.队列的基本操作实现 5.1 初始化队列 5.2 队尾入队列 5.3 队头出队列 5.4 队列中有效元素的个数 5.5 判断队列是否为空 5.6 获取队头数据 5.7 获取队尾的数据 5.8 销毁队列 6.测试 6.1测试 6.2 测试结果 1.思考-1 为什么栈用

  • C语言超详细讲解栈的实现及代码

    C语言超详细讲解栈的实现及代码

    目录 前言 栈的概念 栈的结构 栈的实现 创建栈结构 初始化栈 销毁栈 入栈 出栈 获取栈顶元素 获取栈中有效元素个数 检测栈是否为空 总代码 Stack.h 文件 Stack.c 文件 Test.c 文件 前言 栈的概念 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则.有点类似于手枪弹夹,后压进去的子弹总是最先打出,除非枪坏了. 压栈:栈的插入

  • C语言超详细讲解队列的实现及代码

    C语言超详细讲解队列的实现及代码

    目录 前言 队列的概念 队列的结构 队列的应用场景 队列的实现 创建队列结构 队列初始化 队列销毁 入队列 出队列 队列判空 获取队列元素个数 获取队列头部元素 获取队列尾部元素 总代码 Queue.h 文件 Queue.c 文件 Test.c 文件 前言 队列的概念 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 队列和前文所学的栈

  • C语言超详细讲解函数栈帧的创建和销毁

    C语言超详细讲解函数栈帧的创建和销毁

    目录 1.本节目标 2.相关寄存器 3.相关汇编指令 4.什么是函数栈帧 5.什么是调用堆栈 6.函数栈帧的创建和销毁 (1).main函数栈帧的创建与初始化 (2).main函数的核心代码 (3).Add函数的调用过程 (4).Add函数栈帧的销毁 (5).调用完成 7.对开篇问题的解答 1.本节目标 C语言绝命七连问,你能回答出几个? 局部变量是如何创建的?为什么局部变量不初始化其内容是随机的?有些时候屏幕上输出的"烫烫烫"是怎么来的?函数调用时参数时如何传递的?传参的顺序是怎样的

随机推荐