Leetcode 数组问题3:旋转数组

问题描述: 给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。 示例 : 输入A数组: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋...

问题描述:

给定一个数组,将数组中的元素向右移动 个位置,其中 是非负数。

示例 :

输入A数组: [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]

尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。要求使用空间复杂度为 O(1) 的原地算法。


问题分析:

将数组中的元素向右移动,并要求空间复杂度为O(1),每移动一次,数组的最后一个元素移动到首位,其余元素均向后移动一位,

以上面的A数组为例,可以将A[6]=7先拿出来,不被向后移动的其他数组元素的值覆盖掉,然后将其余元素向后移动一位,数组变为[A[0],1,2,3,4,5,6],再把

A[6]的值赋给A[0],这样就完成了一次数组的移动,循环上述过程即可。这种方法时间复杂度为O(KN),比较耗时

翻转算法:先将数组整个翻转一遍,将后面的元素移动到了前面,但是这时的元素顺序并不满足要求,需要将索引为[0,k-1],和 [k,n-1]的元素翻转回来

时间复杂度为O(n)

 

 以上面的A数组为例:

     [1,2,3,4,5,6,7] --翻转索引为[0,n-1]之间的元素--> [7,6,5,4,3,2,1] --翻转索引为[0,k-1]之间的元素--> [5,6,7,4,3,2,1] --翻转索引为[k,n-1]之间的元素--> [5,6,7,1,2,3,4]

JAVA实现:

class Solution {
    public void rotate(int[] nums, int k) {
        int len=nums.length;
        k=k%len;//移动的长度只需要对原数组长度取余即可,当k=len时,数组不变
        int temp=0;
        if(k==0){}
        else{
            for(int j=0;j<k;j++){              
               temp=nums[len-1];//先将数组最后一个元素的值赋给temp 
             for(int i=len-2;i>=0;i--){
                nums[i+1]=nums[i];//剩余数组元素均向右移动一位
            }
                nums[0]=temp;//数组最后一个元素移动到第一个元素的位置
            }
            
        }
    }
}

class Solution {
//翻转算法
public void rotate(int[] nums, int k) { int n = nums.length; k = k%n; reverse(nums, 0, n - 1); reverse(nums, 0, k - 1); reverse(nums, k, n - 1); } private void reverse(int[] nums, int i, int j) { while (i< j) { int temp = nums[i]; nums[i++] = nums[j]; nums[j--] = temp; } } }




  • 发表于 2019-05-25 19:40
  • 阅读 ( 137 )
  • 分类:网络文章

条评论

请先 登录 后评论
不写代码的码农
小编

篇文章

作家榜 »

  1. 小编 文章
返回顶部
部分文章转自于网络,若有侵权请联系我们删除