Leetcode旋轉數組

收藏待读

Leetcode旋轉數組

1、題目描述

給定一個數組,將數組中的元素向右移動 k 個位置,其中 k 是非負數。

示例 1:

輸入: [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]

示例 2:

輸入: [-1,-100,3,99] 和 k = 2
輸出: [3,99,-1,-100]
解釋: 
向右旋轉 1 步: [99,-1,-100,3]
向右旋轉 2 步: [3,99,-1,-100]

說明:

儘可能想出更多的解決方案,至少有三種不同的方法可以解決這個問題。要求使用空間複雜度為 O(1) 的原地算法。

2、解法

①:整體移動法

以從下標0開始長度為(size – k)的數組集合整體移動k個單位,後面數字的依次往前移動,例如題目中舉出的第1個示例來說,

[1,2,3,4,5,6,7]移動k = 3,也就是以第0個開始長度為(7 – 3 = 4)的數組集合([1,2,3,4])移動3個長度單位

第一次移動: [7,1,2,3,4,5,6]
第二次移動: [6,7,1,2,3,4,5]
第三次移動: [5,6,7,1,2,3,4]
public void rotate(int[] nums, int k) {
        k = k % nums.length;
        if (k == 0)return;
         for(int j = 0;j =j;i--){
                swapNum(nums,i,i+1); 
            }
       }     
}
 public void swapNum(int[] num,int pre,int next){
        if (next > num.length - 1||next  
 

這是正常的思路的解法,但是題目要求是O(1)的時間複雜度,而這個解法的時間複雜度卻是O(n^2),因此不符合題目要求,這也有了下面的兩種解法。

②:翻轉法

這種解法需要畫一個圖來說明,請看下圖。

Leetcode旋轉數組

圖(1):翻轉法原理

哈哈,在這裡請忽略下字體不美觀的因素,還是來關注下主要算法核心,由此圖可以得出,可以分3步走,第一次是從0到(size - k - 1)的翻轉,第二次是(size - k)到size的翻轉,第三次是整體的翻轉。

第一次翻轉: [4,3,2,1,5,6,7]
第二次翻轉: [4,3,2,1,7,6,5]
第三次翻轉: [5,6,7,1,2,3,4]

代碼如下:

public void rotate(int[] nums, int k) {
        k %= nums.length;
        int i = nums.length-k;
        reverse(nums, 0, i-1);
        reverse(nums,i,nums.length-1);
        reverse(nums,0,nums.length-1);
        
    }
    
    private void reverse(int[]nums, int start, int end){
        while(start

③:擴展數組法(以空間換時間)

還是以[1,2,3,4,5,6,7]這個數組為例,可以再增加一個相同的數組成為[1,2,3,4,5,6,7,1,2,3,4,5,6,7],當移動k = 3個時,可以從這個數組得知是從下標(size - k)起長度為size的數組[5,6,7,1,2,3,4]

代碼如下:

public void rotate(int[] nums, int k) {
        k = k % nums.length;
        if (k == 0)return;
        int[] numscopy = new int[nums.length * 2];
        for (int i = 0; i  
 

經測試,可行!

附上leetcode此題鏈接:

https://leetcode-cn.com/problems/rotate-array/

原文 : 簡書

相關閱讀

免责声明:本文内容来源于簡書,已注明原文出处和链接,文章观点不代表立场,如若侵犯到您的权益,或涉不实谣言,敬请向我们提出检举。