亲宝软件园·资讯

展开

C语言双指针旋转数组

乔乔家的龙龙 人气:0

LeetCode题目如下:

在这里插入图片描述

首先这个中等难度我是没搞懂,后面才发现原来中等中在要求多方法上,那就来看看怎么搞定他吧。

暴力思路

首先我说一下我本人的思路,就是函数进行倒序操作,分三步:

1.整体倒序 :1234567-------7654321

2.前半部分倒序:7654321------- 5674321

3.后半部分倒序:5674321-------5671234

由于题目已经给出了我们 k 的值,我们直接暴力思路(注意是暴力思路非暴力求解),双指针交换对应的值就行:

void exchange(int* a, int* b)
{
int n=*a;
*a = *b;
*b = n;
}   //交换a,b位置
void reverse(int* nums,int left,int right)
{
while(left<right)
{
exchange(&nums[left],&nums[right]);
left++;
right--;
}   //对指定范围内元素进行翻转操作
}
void rotate(int* nums, int numsSize, int k){
k%=numsSize;
if(k==0)
{
return ;  //防止k过大或0导致无意义操作
}
reverse(nums,0,numsSize-1);//全倒序
reverse(nums,0,k-1);//前半部分倒序
reverse(nums,k,numsSize-1);//后半部分倒序
}

这种方法直观,最容易想到,特点是思路清晰,完美符合了流程,时间复杂度是O(n),空间复杂度是O(1),将将就就

外加数组

自力更生不想要咱就寻求外援嘛,直接创建一个额外数组,前半部分放前面,后半部分放后面不就行了,用 numsSize 表示数组的长度,我们遍历原数组,将原数组下标为 n 的元素放至新数组下标为 n+k 的位置,最后将新数组拷贝至原数组即可:

void rotate(int* nums, int numsSize, int k){
int arr[numsSize] = {0};
for(int n = 0;n<numsSize;n++)
{
arr[(k+n)%numsSize] = nums[n]; //nums所有元素向前移动 k 个单位,依次存到数组arr
}
for(int n = 0;n<numsSize;n++)
{
nums[n] = arr[n];  //将arr数组内容拷贝回原数组nums
}

同理,我们可以选择直接 malloc 一块空间出来,这种方法同上不赘述

格局抬高

既然我们能想到 malloc 开辟空间操作,那再想想库函数里面好像还有个好东西叫 memcpy ,头文件:#include <string.h>,memcpy() 用来复制内存,且忽略 \0,其原型为:

  void * memcpy ( void * dest, const void * src, size_t num );

memcpy() 会复制 src 所指的内存内容的前 num 个字节到 dest 所指的内存地址上。memcpy() 并不关心被复制的数据类型,只是逐字节地进行复制,这给函数的使用带来了很大的灵活性,可以面向任何数据类型进行复制。

代码如下:

void rotate(int* nums, int numsSize, int k){
int arr[numsSize];
k %= numsSize;
memcpy(arr,nums+(numsSize-k),k*(int)sizeof(int));
memcpy(arr+k,nums,(numsSize-k)*(int)sizeof(int));
memcpy(nums,arr,numsSize*(int)sizeof(int));
}

但是在重叠内存块这方面,memmove() 是比 memcpy() 更安全的方法,所以可能会有一个疑问就是为什么不用 memmove?

memmove 相比 memcpy 更容易造成数据丢失。如果目标区域和源区域有重叠的话,memmove() 能保证源串在被覆盖之前将重叠区域的字节拷贝到目标区域中,复制后源区域的内容会被更改。如果目标区域与源区域没有重叠,则和 memcpy() 函数功能相同。

强调一下,与 strcpy() 不同的是,memcpy() 会完整的复制 num 个字节,不会因为遇到“\0”而结束。

环形替代

在这里插入图片描述

这是力扣上官方给出的一种方法,需要数学推导,比较难理解,解析给的是花里胡哨,添油加醋的,我大概概括一下就是把数组一串元素类比成莫比乌斯环,我们构图理解就简单多了(ppt手绘勿喷):

在这里插入图片描述

什么意思呢,就是我们就拿k作为遍历间隔,不断拿 1+nk(n从0开始) 位置的元素替代 1+ (n+1)k位置元素,直到回到原点,回到原点时因为遍历间隔>0,必定会有未遍历的元素我们只需+1 跳到下一位置继续上述操作,再使用另一单独变量,跟踪当前已经访问的元素数量,当该变量 = 元素数量时遍历完成,结束遍历过程。(个人理解,如有不当请联系我更正哟~)

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);
    }
}

今天就到这里吧,摸了家人们,更多关于多方法超度旋转数组的资料请关注其它相关文章!

加载全部内容

相关教程
猜你喜欢
用户评论