(C语言版)力扣(LeetCode)189. 轮转数组官方3种解法分析

简介: 尽可能想出更多的解决方案,至少有 三种 不同的方法可以解决这个问题。

b6a232ddd08a435b99c509cb8103e77c.png


题目


题目链接:轮转数组


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

示例 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:


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


提示:

1 <= nums.length <= 105

-231 <= nums[i] <= 231 - 1

0 <= k <= 105

进阶:

尽可能想出更多的解决方案,至少有 三种 不同的方法可以解决这个问题。

你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?


第一种解法:额外数组


代码如下:


void rotate(int* nums, int numsSize, int k) {
    int newArr[numsSize];
    for (int i = 0; i < numsSize; ++i) {
        newArr[(i + k) % numsSize] = nums[i];
    }
    for (int i = 0; i < numsSize; ++i) {
        nums[i] = newArr[i];
    }
}


复杂度分析:

时间复杂度: O(n),其中 n 为数组的长度。

空间复杂度: O(n)。

个人分析:

这种解法最妙的地方是(i+k)%numSize的运用,值得多想想,这里是使用了一个变长数组的写法,使用了额外的数组空间接收反转后的数组,再重新赋回原数组。

举个例子:

nums[ ]={1,2,3,4,5},k=2,反转后应是nums[ ]={4,5,1,2,3};


初始条件:i=0  k=2  numsSize=5
第一趟   i=0   (i + k) % numsSize=2    newArr[2]=nums[0]
         newArr[]={ , ,1, , }
第二趟   i=1   (i + k) % numsSize=3    newArr[3]=nums[1]
         newArr[]={ , ,1,2, }
第三趟   i=2   (i + k) % numsSize=4    newArr[4]=nums[2]
         newArr[]={ , ,1,2,3}
第三趟   i=3   (i + k) % numsSize=0    newArr[0]=nums[3]
         newArr[]={4, ,1,2,3}
第四趟   i=4   (i + k) % numsSize=1    newArr[1]=nums[4]
         newArr[]={4,5,1,2,3}
i=numsSize 终止第一个循环


最后将利用for循环将newArr[ ]中的元素遍历赋给nums数组即可。


第二种解法:环状替换


代码如下:


//最大公约数
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
//交换
void swap(int* a, int* b) {
    int t = *a;
    *a = *b, *b = t;
}
void rotate(int* nums, int numsSize, int k) {
    k = k % numsSize;
    int count = gcd(k, numsSize);
    for (int start = 0; start < count; ++start) {
        int current = start;
        int prev = nums[start];
        do {
            int next = (current + k) % numsSize;
            swap(&nums[next], &prev);
            current = next;
        } while (start != current);
    }
}


复杂度分析:

时间复杂度:O(n),其中 n 为数组的长度。每个元素只会被遍历一次。

空间复杂度:O(1)。我们只需常数空间存放若干变量。

个人分析:

首先讲讲这里的gcd函数是一个求最大公约数的自定义函数,有很多小伙伴可能不理解这种写法,可以替换成下面这种常规的辗转相除写法:


int gcd(int a, int b) {
    while(a%b)
    {
        int r=a%b;
        a=b;
        b=r;
    }
    return b;
}


swap是常用的交换函数就不多讲了,这种写法的主要思路是将间隔为k的元素逐个向后替换,再将该间隔最后一个元素与开头替换,求k与numsSize的最大公约数是为了将不同间隔数分组,设定循环次数,便于遍历交换。

举个例子:

nums[ ]={1,2,3,4,5,6},k=2,反转后应是nums[ ]={5,6,1,2,3,4};


初始条件:start=0  k=2  numsSize=6
第一趟 prev=nums[0]=1
       current=0  next=(current + k) % numsSize=2
       nums[2]=1  prev=3  nums[]={1,2,1,4,5,6}
       current=2  next=(current + k) % numsSize=4
       nums[4]=3  prev=5  nums[]={1,2,1,4,3,6}
       current=4  next=(current + k) % numsSize=0
       nums[0]=5  prev=1  nums[]={5,2,1,4,3,6}
       current=0=start  终止do...while循环
第二趟 prev=nums[1]=2
       current=1  next=(current + k) % numsSize=3
       nums[3]=2  prev=4  nums[]={5,2,1,2,3,6}
       current=3  next=(current + k) % numsSize=5
       nums[5]=4  prev=6  nums[]={5,2,1,2,3,4}
       current=5  next=(current + k) % numsSize=1
       nums[1]=6  prev=2  nums[]={5,6,1,2,3,4}
       current=1=start  终止do...while循环
start=2=count  终止for循环


提一下这里的k=k%numsSize操作,我觉得是个优化吧,假设这里k=8,实际和k=2的最终结果是一样的,这样可以做性能上的优化吧,然后就是这里count是用于循环条件的,也可以不使用最大公约数的赋值写法,也可以在while循环里加一个变量记录被访问的元素,当count等于这个值时,结束遍历也可。


第三种解法:翻转数组


代码如下:


//交换
void swap(int* a, int* b) {
    int t = *a;
    *a = *b, *b = t;
}
//数组反转
void reverse(int* nums, int start, int end) {
    while (start < end) {
        swap(&nums[start], &nums[end]);
        start++;
        end++;
    }
}
void rotate(int* nums, int numsSize, int k) {
    k %= numsSize;
    reverse(nums, 0, numsSize - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, numsSize - 1);
}


复杂度分析:

时间复杂度:O(n),其中 n 为数组的长度。每个元素被翻转两次,一共 n 个元素,因此总时间复杂度为 O(2n)=O(n)。

空间复杂度:O(1)。

个人分析:

这个算法的思路是先将整个数组先反转,再将前后两部分分别反转,个人认为比前两种写法更好理解一些。这里的反转的写法是采用前后指针的交换写法。同样的,举个例子:

nums[ ]={1,2,3,4,5},k=2,反转后应是nums[ ]={4,5,1,2,3};


初始条件:  k=2  numsSize=5
第一趟      nums[]={5,4,3,2,1}
第二趟      nums[]={4,5,3,2,1}
第三趟      nums[]={4,5,1,2,3}


结语


这里的解法代码来自力扣官方,作者只是进行了详细的剖析和部分改动

方便大家理解和提升自己,学会多角度观察问题,解决问题。


有兴趣的小伙伴可以关注作者,如果觉得内容不错,请给个一键三连吧,蟹蟹你哟!!!

制作不易,如有不正之处敬请指出

感谢大家的来访,UU们的观看是我坚持下去的动力

在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!

9fe83f8c4dbc472a813a8a4657c6d5c7.png

相关文章
|
1月前
|
传感器 算法 安全
【C语言】两个数组比较详解
比较两个数组在C语言中有多种实现方法,选择合适的方法取决于具体的应用场景和性能要求。从逐元素比较到使用`memcmp`函数,再到指针优化,每种方法都有其优点和适用范围。在嵌入式系统中,考虑性能和资源限制尤为重要。通过合理选择和优化,可以有效提高程序的运行效率和可靠性。
89 6
|
2月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
68 5
|
2月前
|
存储 程序员 编译器
C 语言数组与指针的深度剖析与应用
在C语言中,数组与指针是核心概念,二者既独立又紧密相连。数组是在连续内存中存储相同类型数据的结构,而指针则存储内存地址,二者结合可在数据处理、函数传参等方面发挥巨大作用。掌握它们的特性和关系,对于优化程序性能、灵活处理数据结构至关重要。
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
65 1
|
2月前
|
存储 C语言 计算机视觉
在C语言中指针数组和数组指针在动态内存分配中的应用
在C语言中,指针数组和数组指针均可用于动态内存分配。指针数组是数组的每个元素都是指针,可用于指向多个动态分配的内存块;数组指针则指向一个数组,可动态分配和管理大型数据结构。两者结合使用,灵活高效地管理内存。
|
2月前
|
存储 NoSQL 编译器
C 语言中指针数组与数组指针的辨析与应用
在C语言中,指针数组和数组指针是两个容易混淆但用途不同的概念。指针数组是一个数组,其元素是指针类型;而数组指针是指向数组的指针。两者在声明、使用及内存布局上各有特点,正确理解它们有助于更高效地编程。
|
2月前
|
存储 人工智能 算法
数据结构实验之C 语言的函数数组指针结构体知识
本实验旨在复习C语言中的函数、数组、指针、结构体与共用体等核心概念,并通过具体编程任务加深理解。任务包括输出100以内所有素数、逆序排列一维数组、查找二维数组中的鞍点、利用指针输出二维数组元素,以及使用结构体和共用体处理教师与学生信息。每个任务不仅强化了基本语法的应用,还涉及到了算法逻辑的设计与优化。实验结果显示,学生能够有效掌握并运用这些知识完成指定任务。
60 4
|
3月前
|
存储 编译器 C语言
【c语言】数组
本文介绍了数组的基本概念及一维和二维数组的创建、初始化、使用方法及其在内存中的存储形式。一维数组通过下标访问元素,支持初始化和动态输入输出。二维数组则通过行和列的下标访问元素,同样支持初始化和动态输入输出。此外,还简要介绍了C99标准中的变长数组,允许在运行时根据变量创建数组,但不能初始化。
62 6
|
4月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
5月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
130 2