【02】右旋函数(C语言)

2024-02-11 10:20
文章标签 语言 函数 02 右旋

本文主要是介绍【02】右旋函数(C语言),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

题目:给定一个整数数组nums,将数组中的元素向右轮转k个位置,其中k是非负数。

1.暴力求解(轮转k次)

2. 三段逆置求解

①逆置函数

②轮转函数

3.空间换时间求解



题目:给定一个整数数组nums,将数组中的元素向右轮转k个位置,其中k是非负数。

例如:

nums[7] = {1,2,3,4,5,6,7}    k = 3

右旋三次后nums=[5,6,7,1,2,3,4]

1.暴力求解(轮转k次)

向右旋转 1 次:[7,1,2,3,4,5,6]

向右旋转 2 次:[6,7,1,2,3,4,5]

向右旋转 3 次:[5,6,7,1,2,3,4]

注:①如果k大于数组的总长度的话函数需要重复轮转多次,这时可以取模运算(也就是求余数)

       ②向右轮转时最后一个元素需要保存起来防止遗失,最后再将保存的最后一个元素的值赋给               第一个元素完成一次轮转;

       ③运用for循环轮转k次;

void rotate(int* nums,int numsSize, int k)
{k %= numsSize;//k大于numsSize取模,避免不必要的计算,小于numsSize取模则没有影响int i = 0;int tmp = 0;for (i = 0; i < k; i++){int a = numsSize;tmp = nums[a - 1];创建一个变量保存最后的数字while (a >= 2)//当(a-2)>=0时判定条件结束{nums[a - 1] = nums[a - 2];//将数组前一个值赋给后一个a--;}nums[0] = tmp;//将tmp中保存的数组最后一个元素的值赋给数组第一个元素}
}

 在vs2022上完整代码实现如下:

#include<stdio.h>
void rotate(int* nums,int numsSize, int k)
{k %= numsSize;//k大于numsSize取模,避免不必要的计算,小于numsSize取模则没有影响int i = 0;int tmp = 0;for (i = 0; i < k; i++){int a = numsSize;tmp = nums[a - 1];创建一个变量保存最后的数字while (a >= 2)//当(a-2)>=0时判定条件结束{nums[a - 1] = nums[a - 2];//将数组前一个值赋给后一个a--;}nums[0] = tmp;//将tmp中保存的数组最后一个元素的值赋给数组第一个元素}
}int main()
{int nums[7] = { 1,2,3,4,5,6,7 };int k = 3;rotate(nums,7, k);for (int i = 0; i < 7; i++)//打印轮转后的数组{printf("%d\n", nums[i]);}return 0;
}

运行结果如下:

以上就是暴力求解啦,关键是要一次一次的轮转,其时间复杂度为O(n^{2}),空间复杂度为O(1),对每次轮转的代码理解也极其重要哦~

2. 三段逆置求解

      @_@: "一个不一样的玩法,极其灵活的同时又极其难想,但它又像欧亨利式的结尾那般出人意料却又在情理之中"。

nums=[1,2,3,4,5,6,7]          k=3           n=7

①逆置函数

void reverse(int* nums, int left, int right)//逆置函数
{int tmp = 0;//创建一个中间变量while (left < right)//当左边等于右边时逆置结束{tmp = nums[right];nums[right] = nums[left];nums[left] = tmp;//左边和右边交换left++;right--;}}

②轮转函数

void rotate(int* nums, int numsSize, int k)//轮转函数
{k %= numsSize;reverse(nums, 0, numsSize - k - 1);//前n-k个逆置reverse(nums,0,3)reverse(nums, numsSize - k, numsSize - 1);后k个逆置//reversez(nums,4,6)reverse(nums, 0, numsSize - 1);//整体逆置reverse(nums,0,6)}

在vs2022上运行代码如下:

#include<stdio.h>
void reverse(int* nums, int left, int right)
{int tmp = 0;while (left < right){tmp = nums[right];nums[right] = nums[left];nums[left] = tmp;left++;right--;}
}
void rotate(int* nums, int numsSize, int k)
{k %= numsSize;reverse(nums, 0, numsSize - k - 1);//reverse(nums,0,3)reverse(nums, numsSize - k, numsSize - 1);//reversez(nums,4,6)reverse(nums, 0, numsSize - 1);//reverse(nums,0,6)}
int main()
{int nums[7] = { 1,2,3,4,5,6,7 };int k = 3;rotate(nums, 7, 3);for (int i = 0; i < 7; i++){printf("%d\n", nums[i]);}return 0;
}

结果如下:

 以上就是三段逆置啦,其时间复杂度为O(n),空间复杂度为O(1);最重要的就是它的思路三段逆置,其次就是逆置函数的实现。

3.空间换时间求解

开始:nums=[1,2,3,4,5,6,7]

结果:nums=[5,6,7,1,2,3,4]

所以如果有另外一个数组a先将nums中的{5,6,7}保存下来,再将{1,2,3,4}保存即可得到a=[5,6,7,1,2,3,4];最后将a拷贝到nums中即可,其时间复杂度较暴力求解大大减少为O(n),但空间复杂度变多为O(n);

注:①使用malloc开辟空间给a;

        ②使用memcpy函数来拷贝;(malloc、memcpy详情可见上一篇博客动态内存函数介绍【C语言】动态内存函数介绍-CSDN博客)

        ③malloc开辟的空间要记得free释放掉,并将指针置空

代码如下:

void rotate(int* nums, int numsSize, int k)
{k %= numsSize;int* a = (int*)malloc(sizeof(int) * numsSize);memcpy(a, nums + k +1 , sizeof(int) * (numsSize - k -1));//先将nums中的{5,6,7}保存下来memcpy(a + k,nums, sizeof(int) *(k+1));//再将{1,2,3,4}保存memcpy(nums, a, sizeof(int) * numsSize);//最后将a拷贝到nums中free(a);//释放掉开辟的空间a = NULL;//置空指针
}

在vs2022上完整运行代码如下:

void rotate(int* nums, int numsSize, int k)
{k %= numsSize;int* a = (int*)malloc(sizeof(int) * numsSize);memcpy(a, nums + k +1 , sizeof(int) * (numsSize - k -1));memcpy(a + k,nums, sizeof(int) *(k+1));memcpy(nums, a, sizeof(int) * numsSize);free(a);a = NULL;
}
int main()
{int nums[7] = { 1,2,3,4,5,6,7 };int k = 3;rotate(nums, 7, 3);for (int i = 0; i < 7; i++){printf("%d\n", nums[i]);}return 0;
}

运行结果如下:

以上就是空间换时间的方法啦,需要借助C语言中动态内存函数,对于动态内存函数的学习也必不可少哦,【C语言】动态内存函数介绍-CSDN博客

这篇关于【02】右旋函数(C语言)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/699546

相关文章

Kotlin 作用域函数apply、let、run、with、also使用指南

《Kotlin作用域函数apply、let、run、with、also使用指南》在Kotlin开发中,作用域函数(ScopeFunctions)是一组能让代码更简洁、更函数式的高阶函数,本文将... 目录一、引言:为什么需要作用域函数?二、作用域函China编程数详解1. apply:对象配置的 “流式构建器”最

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

利用Go语言开发文件操作工具轻松处理所有文件

《利用Go语言开发文件操作工具轻松处理所有文件》在后端开发中,文件操作是一个非常常见但又容易出错的场景,本文小编要向大家介绍一个强大的Go语言文件操作工具库,它能帮你轻松处理各种文件操作场景... 目录为什么需要这个工具?核心功能详解1. 文件/目录存javascript在性检查2. 批量创建目录3. 文件

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量(推荐)2.相加和相减的方式(值较大时可能丢失数据)3.按位异或运算1.使用临时

使用C语言实现交换整数的奇数位和偶数位

《使用C语言实现交换整数的奇数位和偶数位》在C语言中,要交换一个整数的二进制位中的奇数位和偶数位,重点需要理解位操作,当我们谈论二进制位的奇数位和偶数位时,我们是指从右到左数的位置,本文给大家介绍了使... 目录一、问题描述二、解决思路三、函数实现四、宏实现五、总结一、问题描述使用C语言代码实现:将一个整

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

kotlin的函数forEach示例详解

《kotlin的函数forEach示例详解》在Kotlin中,forEach是一个高阶函数,用于遍历集合中的每个元素并对其执行指定的操作,它的核心特点是简洁、函数式,适用于需要遍历集合且无需返回值的场... 目录一、基本用法1️⃣ 遍历集合2️⃣ 遍历数组3️⃣ 遍历 Map二、与 for 循环的区别三、高

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st