189. 旋转数组

x33g5p2x  于10个月前 转载在 其他  
字(1.3k)|赞(0)|评价(0)|浏览(88)

旋转数组

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

  • 进阶:
    尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
    你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?
  • 示例:
    输入: nums = [1,2,3,4,5,6,7], k = 3
    输出: [5,6,7,1,2,3,4]

解题思路

最简单的重建一个同样大小的数组,则满足(i+k)mod(len) 处的位置的值为原数组 i 位置的值。空间复杂度为O(N)
我们也可以构造部分数组,大小为k mod(len) 只需要将后面k个元素提前存储起来就可以了。然后挨个循环移位就可以,时间相对第一种会节约一些。同时空间也会节约,空间复杂度为O(K), 这里的k是常量。按理说可以算做O(1). 但是相比较下一种,空间还是较多的。
最后一种应该是时间和空间都毕竟均衡的方法。也就是牺牲时间来换空间。利用三次反转就可以了

代码实现

  • 1
class Solution {
    public void rotate(int[] nums, int k) {
        int temp;
        int len = nums.length;
        k = k % len;
        int[] tempNums = new int[len];
        for(int i = 0 ; i < len ; i++)
        {
            tempNums[(i + k) % len] = nums[i];
        }
        
        for(int i = 0 ; i < len ; i++)
        {
            temp = nums[i];
            nums[i] = tempNums[i];
            tempNums[i]= temp;
        }
        
    }
}
  • 2
class Solution {
    public void rotate(int[] nums, int k) {
        int temp;
        int len = nums.length;
        k = k % len;
        int[] numsk = new int[k];
        for(int i = 0 ; i < k ; i++)
        {
            numsk[i] = nums[len - k + i];
        }
        for(int i = len - 1; i >=k; i--){
            temp = nums[i];
            nums[i] = nums[i-k];
            nums[i-k] = temp;
        }
        for(int i = 0 ; i < k ; i++)
        {
            nums[i] = numsk[i];
        }
        
    }
}
  • 3
class Solution {
    public void rotate(int[] nums, int k) {
        int temp;
        int len = nums.length;
        k = k % len;
        for(int i = 0; i < len / 2; i++){
            temp = nums[i];
            nums[i] = nums[len-1-i];
            nums[len - 1 -i] = temp;
        }

        for(int i = 0; i < k / 2; i ++){
            temp = nums[i];
            nums[i] = nums[k-1-i];
            nums[k - 1 -i] = temp;
        }

        for(int i = k; i < (len - k) / 2 + k; i ++){
            temp = nums[i];
            nums[i] = nums[len + k-1-i];
            nums[len + k - 1 -i] = temp;
        }
        
    }
}

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/rotate-array
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

相关文章