力扣---LeetCode189.轮转数组

2023-06-28 75

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 第二弹——力扣LeetCode每日一题

前言

能给你带来快乐的不止谈恋爱还有努力的成就感.

本章的内容是力扣每日随机一题的部分方法的解析

提示：以下是本篇文章正文内容，下面案例可供参考

189.轮转数组

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

方法一：暴力求解，旋转k次

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

方法二：三段逆置

时间复杂度：O(N)

空间复杂度：O(1)

void reverse(int* a,int left,int right)
{
    while(left<right)
    {
        int tmp=a[left];
        a[left]=a[right];
        a[right]=tmp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k)
{
    if(k>numsSize)
    {
        k%=numsSize;
    }
    reverse(nums,0,numsSize-k-1);
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-1);
}

方法三：空间换时间

时间复杂度：O(N)

空间复杂度：O(N)

void rotate(int* nums, int numsSize, int k)
{
    if(k>numsSize)
    {
        k%=numsSize;
    }
    int* tmp=(int*)malloc(sizeof(int)*numsSize);
    memcpy(tmp+k,nums,sizeof(int)*(numsSize-k));
    memcpy(tmp,nums+numsSize-k,sizeof(int)*k);
    memcpy(nums,tmp,sizeof(int)*numsSize);
    free(tmp);
    tmp=NULL;
}