[LeetCode] 189. Rotate Array 旋轉(zhuǎn)數(shù)組

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input:

[1,2,3,4,5,6,7]

and k = 3

Output:

[5,6,7,1,2,3,4]

Explanation:

rotate 1 steps to the right:

[7,1,2,3,4,5,6]

rotate 2 steps to the right:

[6,7,1,2,3,4,5]

rotate 3 steps to the right:

[5,6,7,1,2,3,4]

Example 2:

Input:

[-1,-100,3,99]

and k = 2
Output: [3,99,-1,-100]
Explanation:
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note:

• Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
• Could you do it in-place with O(1) extra space? 

新題搶先刷，這道題標(biāo)為 Easy，應(yīng)該不是很難，我們先來(lái)看一種 O(n) 的空間復(fù)雜度的方法，我們復(fù)制一個(gè)和 nums 一樣的數(shù)組，然后利用映射關(guān)系 i -> (i+k)%n 來(lái)交換數(shù)字。代碼如下：

解法一：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        vector<int> t = nums;
        for (int i = 0; i < nums.size(); ++i) {
            nums[(i + k) % nums.size()] = t[i];
        }
    }
};

由于提示中要求我們空間復(fù)雜度為 O(1)，所以我們不能用輔助數(shù)組，上面的思想還是可以使用的，但是寫(xiě)法就復(fù)雜的多，而且需要用到很多的輔助變量，我們還是要將 nums[idx] 上的數(shù)字移動(dòng)到 nums[(idx+k) % n] 上去，為了防止數(shù)據(jù)覆蓋丟失，我們需要用額外的變量來(lái)保存，這里用了 pre 和 cur，其中 cur 初始化為了數(shù)組的第一個(gè)數(shù)字，然后當(dāng)然需要變量 idx 標(biāo)明當(dāng)前在交換的位置，還需要一個(gè)變量 start，這個(gè)是為了防止陷入死循環(huán)的，初始化為0，一旦當(dāng) idx 變到了 strat 的位置，則 start 自增1，再賦值給 idx，這樣 idx 的位置也改變了，可以繼續(xù)進(jìn)行交換了。舉個(gè)例子，假如 [1, 2, 3, 4], K=2 的話，那么 idx=0，下一次變?yōu)?idx = (idx+k) % n = 2，再下一次又變成了 idx = (idx+k) % n = 0，此時(shí)明顯 1 和 3 的位置還沒(méi)有處理過(guò)，所以當(dāng)我們發(fā)現(xiàn) idx 和 start 相等，則二者均自增1，那么此時(shí) idx=1，下一次變?yōu)?idx = (idx+k) % n = 3，就可以交換完所有的數(shù)字了。

因?yàn)殚L(zhǎng)度為n的數(shù)組只需要更新n次，所以我們用一個(gè) for 循環(huán)來(lái)處理n次。首先 pre 更新為 cur，然后計(jì)算新的 idx 的位置，然后將 nums[idx] 上的值先存到 cur 上，然后把 pre 賦值給 nums[idx]，這相當(dāng)于把上一輪的 nums[idx] 賦給了新的一輪，完成了數(shù)字的交換，然后 if 語(yǔ)句判斷是否會(huì)變到處理過(guò)的數(shù)字，參見(jiàn)上面一段的解釋，我們用題目中的例子1來(lái)展示下面這種算法的 nums 的變化過(guò)程：

1 2 3 4 5 6 7
1 2 3 1 5 6 7
1 2 3 1 5 6 4
1 2 7 1 5 6 4
1 2 7 1 5 3 4
1 6 7 1 5 3 4
1 6 7 1 2 3 4
5 6 7 1 2 3 4

解法二：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.empty() || (k %= nums.size()) == 0) return;
        int start = 0, idx = 0, pre = 0, cur = nums[0], n = nums.size();
        for (int i = 0; i < n; ++i) {
            pre = cur;
            idx = (idx + k) % n;
            cur = nums[idx];
            nums[idx] = pre;
            if (idx == start) {
                idx = ++start;
                cur = nums[idx];
            }
        }
    }
};

這道題其實(shí)還有種類似翻轉(zhuǎn)字符的方法，思路是先把前 n-k 個(gè)數(shù)字翻轉(zhuǎn)一下，再把后k個(gè)數(shù)字翻轉(zhuǎn)一下，最后再把整個(gè)數(shù)組翻轉(zhuǎn)一下：

1 2 3 4 5 6 7
4 3 2 1 5 6 7
4 3 2 1 7 6 5
5 6 7 1 2 3 4

解法三：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.empty() || (k %= nums.size()) == 0) return;
        int n = nums.size();
        reverse(nums.begin(), nums.begin() + n - k);
        reverse(nums.begin() + n - k, nums.end());
        reverse(nums.begin(), nums.end());
    }
};

由于旋轉(zhuǎn)數(shù)組的操作也可以看做從數(shù)組的末尾取k個(gè)數(shù)組放入數(shù)組的開(kāi)頭，所以我們用 STL 的 push_back 和 erase 可以很容易的實(shí)現(xiàn)這些操作。

解法四：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.empty() || (k %= nums.size()) == 0) return;
        int n = nums.size();
        for (int i = 0; i < n - k; ++i) {
            nums.push_back(nums[0]);
            nums.erase(nums.begin());
        }
    }
};

下面這種方法其實(shí)還蠻獨(dú)特的，通過(guò)不停的交換某兩個(gè)數(shù)字的位置來(lái)實(shí)現(xiàn)旋轉(zhuǎn)，根據(jù)網(wǎng)上這個(gè)帖子的思路改寫(xiě)而來(lái)，數(shù)組改變過(guò)程如下：

1 2 3 4 5 6 7
5 2 3 4 1 6 7
5 6 3 4 1 2 7
5 6 7 4 1 2 3
5 6 7 1 4 2 3
5 6 7 1 2 4 3
5 6 7 1 2 3 4

解法五：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (nums.empty()) return;
        int n = nums.size(), start = 0;   
        while (n && (k %= n)) {
            for (int i = 0; i < k; ++i) {
                swap(nums[i + start], nums[n - k + i + start]);
            }
            n -= k;
            start += k;
        }
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(189.旋轉(zhuǎn)數(shù)組)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)旋轉(zhuǎn)數(shù)組內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論