锐客网

  1. 首页 > it技术 > >

leetcode刷题记录|轮转数组——LeetCode198题

算法leetcodec++LeetCode刷题记录


文章目录

  • 前言
  • 暴力循环（超时）
  • 额外数组
    • 环状替换
    • 数组翻转（最优解）
  • 总结

前言 最近在刷LeetCode算法入门题，仅做学习笔记用。基本上引用的都是力扣官方解答。
暴力循环（超时） 暴力循环k次，每次右移一位。
运行超时，显然，当数值包含的数很多或k值太大时，会消耗太多时间。
时间复杂度O(n^2)
//数组元素向右轮转k void rotate(vector& nums, int k) { int n = nums.size(); for(int j=0; j0; i--){ nums[i] = nums[i-1]; } nums[0] = temp; } cout<<"["; for(int i=0; i

额外数组 创建一个跟输入数组一样大的空数组，将每个数的值安装轮转结束后的顺序依次填入新数组。
void rotate(vector& nums, int k) { int n = nums.size(); vector ans(n); for(int i=0; i

时间复杂度O(n)
空间复杂度O(n)
缺点：内存消耗较大
环状替换 使用额外数组的原因在于，如果我们直接将每个数字放至它最后的位置，被放置的元素会被覆盖。因此我们将每次替换的元素保存带变量temp中。
令初始temp=nums[0]，根据规则，位置0的元素会放在 (0+k)%n 位置。再令x = (0+k)%n ，nums[x]=temp，temp值更新为最近被替换的元素。
当x回到初始位置0时，有些数字可能还没有遍历到，所以我们应该考虑程序运行结束的标志是什么？当我们从0遍历，又回到起点0的过程中，我们遍历了多少个元素？
不妨设恰好走过了a圈，该过程共遍历了b个元素，则 an = bk，an是n，k的最小公倍数，因此b = lcm(n,k)/k。
说明单次遍历会访问b个元素，要遍历全部元素，则需要遍历n/b次。
【leetcode刷题记录|轮转数组——LeetCode198题】代码如下（示例）：
void rotate(vector& nums, int k){ int n = nums.size(); k = k%n; int count=gcd(k,n); //k,n的最大公约数，表示需要遍历的次数 for(int start = 0; start

时间复杂度：O（n）// n为数组的长度，每个元素只会被遍历一遍
空间复杂度：O（1）
数组翻转（最优解） 我们将数组的元素向右移动k次后，尾部的k%n个元素就被移至数组头部，其余元素向后移动k%n个位置。
我们先将所有元素翻转，这样尾部的 k%n 个元素就被移至数组头部，然后我们再分别翻转[0, k%n-1]区间和[k%n,n-1]区间的元素就能得到最后的答案。
代码如下（示例）：
void reverse(vector& nums, int start, int end){ while(start& nums, int k){ int n = nums.size(); k = k % n; reverse(nums,0,n-1); reverse(nums,0,k-1); reverse(nums,k,n-1); }

时间复杂度：O(2n) = O(n)//每个元素被翻转两次
空间复杂度：O(1)
总结 优先考虑时间复杂度和空间复杂的较低的算法。

    推荐阅读


    上一篇：多线程|详解 Java 创建线程的三种方式

    下一篇：最小生成树-克鲁斯卡尔算法(Kruskal算法)