前言

2019.10.27日打卡

算法，即解決問(wèn)題的方法。同一個(gè)問(wèn)題，使用不同的算法，雖然得到的結(jié)果相同，但是耗費(fèi)的時(shí)間和資源是不同的。這就需要我們學(xué)習(xí)算法，找出哪個(gè)算法更好。

題目

每天一道leetcode189. 旋轉(zhuǎn)數(shù)組
分類： 數(shù)組
難度： 簡(jiǎn)單
題目鏈接: https://leetcode-cn.com/problems/rotate-array/

題目描述

給定一個(gè)數(shù)組，將數(shù)組中的元素向右移動(dòng) k 個(gè)位置，其中 k 是非負(fù)數(shù)。

示例 1:

輸入: [1,2,3,4,5,6,7] 和 k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右旋轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右旋轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右旋轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]

示例 2:

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

說(shuō)明：

• 盡可能想出更多的解決方案，至少有三種不同的方法可以解決這個(gè)問(wèn)題。
• 要求使用空間復(fù)雜度為 O(1) 的 原地 算法。

題解

自己做

• 思路

我太菜了，感覺(jué)原地移動(dòng)的好復(fù)雜，只好使用額外內(nèi)存來(lái)實(shí)現(xiàn)。即將數(shù)組放入列表中，由于列表可以對(duì)頭尾進(jìn)行操作，因?yàn)槊肯蛴乙苿?dòng)一位，從尾部刪除，將刪除的元素在插入到頭部即可實(shí)現(xiàn)。

• 代碼實(shí)現(xiàn)

class Solution {
    public void rotate(int[] nums, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0; i<nums.length; i++){
            list.add(nums[i]);
        }
        for(int i = 0; i < k; i++) {
            int target = list.remove(nums.length-1);
            list.add(0,target);
        }
        int[] array = new int[]{};
        for (int i =0;i<list.size();i++) {
            nums[i] = list.get(i);
        }
    }
}

代碼比較簡(jiǎn)單，也沒(méi)有什么需要具體解析的，這里使用了額外內(nèi)存，將數(shù)組元素放到列表中。理應(yīng)是不符合題目要求的，不過(guò)沒(méi)辦法，畢竟算法太菜了，下面會(huì)有最優(yōu)解。

• 復(fù)雜度分析

1. 時(shí)間復(fù)雜度：O(n+n+n) = O(n)。 for 循環(huán)的時(shí)間復(fù)雜度是 O(n),一共使用了三次for循環(huán)。
2. 空間復(fù)雜度：O(n)。List需要的空間跟nums中元素個(gè)數(shù)相等。

• 執(zhí)行結(jié)果

image

參考解法

• 思路

本題提供下列兩種思路：

1. 雙重循環(huán)：
   暴力，第一層循環(huán)為需要右移的個(gè)數(shù)，第二層循環(huán)移動(dòng)所有元素值到正確的位置（這個(gè)需要反思，應(yīng)該能想到的，不過(guò)不推薦）。
2. 翻轉(zhuǎn)：
   arr = [1,2,3,4,5] --右移兩位--> [4,5,1,2,3] ,假設(shè) n = arr.length，k = 右移位數(shù)，可得：

翻轉(zhuǎn)索引為[0,n-1]之間的元素--> [5,4,3,2,1]

翻轉(zhuǎn)索引為[0,k-1]之間的元素--> [4,5,3,2,1]

翻轉(zhuǎn)索引為[k,n-1]之間的元素--> [4,5,1,2,3]

旋轉(zhuǎn)數(shù)組其實(shí)就是把數(shù)組分成了兩部分，解題關(guān)鍵就是在保證原有順序的情況下
把后面一部分移到前面去。數(shù)組整體翻轉(zhuǎn)滿足了第二個(gè)要素，但是打亂了數(shù)組的
原有順序，所以此時(shí)再次對(duì)兩部分進(jìn)行翻轉(zhuǎn)，讓他們恢復(fù)到原有順序（翻轉(zhuǎn)之后
再翻轉(zhuǎn)，就恢復(fù)成原有順序了）。

• 代碼實(shí)現(xiàn)

    /**
     * 雙重循環(huán)
     * 時(shí)間復(fù)雜度：O(kn)
     * 空間復(fù)雜度：O(1)
     */
    public void rotate_1(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        for (int i = 0; i < k; i++) {
            int temp = nums[n - 1];
            for (int j = n - 1; j > 0; j--) {
                nums[j] = nums[j - 1];
            }
            nums[0] = temp;
        }
    }

    /**
     * 翻轉(zhuǎn)
     * 時(shí)間復(fù)雜度：O(n)
     * 空間復(fù)雜度：O(1)
     */
    public void rotate_2(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }


    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start++] = nums[end];
            nums[end--] = temp;
        }
    }

• 算法復(fù)雜度分析

雙重for循環(huán):

• 時(shí)間復(fù)雜度：O(n?k)
• 空間復(fù)雜度：O(1)

翻轉(zhuǎn):

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)

執(zhí)行結(jié)果

翻轉(zhuǎn)執(zhí)行結(jié)果：

image

結(jié)束語(yǔ)

小伙伴們可能在看了翻轉(zhuǎn)這種解法，都會(huì)感到非常的巧妙，是怎么想到的。這個(gè)我覺(jué)得不必過(guò)于糾結(jié)，本身我們聯(lián)系算法題，就是一個(gè)刻意提高的過(guò)程，做的多了，自然而然也就有想法了。

【本文最先發(fā)布于此站，轉(zhuǎn)載請(qǐng)注明來(lái)源】： http://coderluo.top