【C语言刷题系列】轮转数组

倔强的石头_

发布于 2024-12-06 18:55:12

1560

文章被收录于专栏：C/C++指南C/C++指南

一、问题描述

注意：

根据题目示例，右转是每次将数组的最右边的一个元素移动到数组最左边

二、解决思路

思路一:两层循环移动元素

时间复杂度O（n^2） 将数组旋转（k%numsSize)轮， 每轮将最后一个元素移动到最前面，其他元素向后移动一位，元素总共移动numsSize次 某种程度上来说，这种解法算是暴力解法，效率是比较低的

思路二:数组三段逆置

时间复杂度O（n） k=k%numsSize（实际旋转次数） 先将数组左半段下标0到numsSize-k-1逆置 再将数组右半段下标numsSize-k到numsSize-1逆置 最后将数组整体下标0到numsSize-1逆置 三段逆置代码几乎是相同的，所以可以单独封装一个逆置函数

三、C语言实现代码

思路一实现代码：

void rotate(int* nums, int numsSize, int k) 
{
    k%=numsSize;
    while(k--)//外循环，控制轮转次数
    {
        int tmp=nums[numsSize-1];//先保存尾部元素
        for(int i=numsSize-1;i>0;i--)//内层循环控制元素移动
        {
            nums[i]=nums[i-1];
        }
        nums[0]=tmp;
    }
}

思路二实现代码：

void reverse(int* nums,int left,int right)//逆置函数
{
    while(left<right)
    {
        int tmp=nums[left];
        nums[left]=nums[right];
        nums[right]=tmp;
        left++;
        right--;
    }
}

void rotate(int* nums, int numsSize, int k) 
{
    k%=numsSize;
    reverse(nums,0,numsSize-k-1);//左段逆置
    reverse(nums,numsSize-k,numsSize-1);//右段逆置
    reverse(nums,0,numsSize-1);//整体逆置
}

个人主页： 倔强的石头的博客

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-12-06，如有侵权请联系 cloudcommunity@tencent.com 删除

博客