快捷導(dǎo)航

在C++中實現(xiàn)高效的數(shù)組原地輪轉(zhuǎn)的方法總結(jié)

更新時間：2025年04月11日 11:27:17 作者：Lion 萊恩呀

在 C++ 中,可以通過多種方式實現(xiàn)數(shù)組的輪轉(zhuǎn)操作,以下是幾種常見的實現(xiàn)方法及其對應(yīng)的代碼示例,文中通過代碼示例介紹的非常詳細(xì),具有一定的參考價值,需要的朋友可以參考下

一、問題：數(shù)組輪轉(zhuǎn)

給定一個長度為 n 的整數(shù)數(shù)組 nums，請將數(shù)組中的元素向右輪轉(zhuǎn) k 個位置，其中 k 是非負(fù)數(shù)。

示例：

輸入：nums = [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]

要求：

實現(xiàn)數(shù)組的右輪轉(zhuǎn)功能。
盡可能探索多種解決方案。 至少思考三種不同的算法思路。
挑戰(zhàn)： 能否設(shè)計一個 空間復(fù)雜度為 O(1) 的原地算法 來解決此問題？嘗試優(yōu)化解決方案，使其具有盡可能高的效率。
分析提出的每種解決方案的時間復(fù)雜度和空間復(fù)雜度。

提示：

考慮 k 大于數(shù)組長度 n 的情況。
仔細(xì)思考數(shù)組輪轉(zhuǎn)的本質(zhì)，嘗試從不同的角度分解問題。

二、問題分析

數(shù)組輪轉(zhuǎn)的本質(zhì)是將數(shù)組中的元素整體向右移動 k 個位置，超出數(shù)組邊界的元素會“循環(huán)”回到數(shù)組的開頭。

關(guān)鍵點：

k 的有效性： 當(dāng) k 大于等于數(shù)組長度 n 時，實際輪轉(zhuǎn)的步數(shù)是 k % n。例如，如果 n = 7，k = 9，那么實際輪轉(zhuǎn) 2 步。因此，需要對 k 進行取模運算。
實現(xiàn)空間復(fù)雜度為 O(1) 的原地算法是難點。這意味著不能使用額外的數(shù)組來存儲臨時結(jié)果。
效率： 如何盡可能減少元素移動的次數(shù)，提高算法效率。

思路 1：暴力法（重復(fù)移動）。

將數(shù)組的最后一個元素移動到第一個位置，其他元素依次向右移動。
重復(fù)這個過程 k 次。
優(yōu)點： 實現(xiàn)簡單，容易理解。
缺點： 時間復(fù)雜度高，效率低，為 O(n * k)。當(dāng) k 接近 n 時，效率非常差。

思路 2：使用額外數(shù)組。

創(chuàng)建一個新的數(shù)組 new_nums，長度與原數(shù)組相同。
將原數(shù)組 nums 中的每個元素 nums[i] 放到新數(shù)組的 new_nums[(i + k) % n] 位置上。
將新數(shù)組 new_nums 復(fù)制回原數(shù)組 nums。
優(yōu)點： 時間復(fù)雜度較低，為 O(n)。
缺點： 需要額外的 O(n) 空間，不滿足原地算法的要求。

思路 3：反轉(zhuǎn)數(shù)組。

將整個數(shù)組反轉(zhuǎn)。
將數(shù)組的前 k % n 個元素反轉(zhuǎn)。
將數(shù)組的后 n - (k % n) 個元素反轉(zhuǎn)。
原理：
- 例如 nums = [1, 2, 3, 4, 5, 6, 7], k = 3
- 反轉(zhuǎn)整個數(shù)組：[7, 6, 5, 4, 3, 2, 1]
- 反轉(zhuǎn)前 k 個元素：[5, 6, 7, 4, 3, 2, 1]
- 反轉(zhuǎn)后 n-k 個元素：[5, 6, 7, 1, 2, 3, 4]
優(yōu)點： 時間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)，滿足原地算法的要求。
缺點： 需要對數(shù)組進行三次反轉(zhuǎn)操作，理解起來稍微復(fù)雜一些。

思路 4：循環(huán)替換。

從位置 0 開始，將該位置的元素移動到 (0 + k) % n 位置，再將該位置的元素移動到 (0 + 2k) % n 位置，以此類推。
為了避免重復(fù)循環(huán)，需要記錄已經(jīng)訪問過的位置，或者使用一個計數(shù)器來控制循環(huán)的次數(shù)。
優(yōu)點： 空間復(fù)雜度為 O(1)。
缺點： 實現(xiàn)相對復(fù)雜，需要仔細(xì)處理循環(huán)的邊界條件。時間復(fù)雜度O(n)。

思路 5：使用GCD（最大公約數(shù)）來優(yōu)化循環(huán)替換。

如果 n 和 k 的最大公約數(shù)是 1，那么只需要一個循環(huán)就能完成所有的替換。但如果最大公約數(shù)不是1，則需要多個循環(huán)。
找到 n 和 k 的最大公約數(shù) gcd。循環(huán)從 0 到 gcd - 1。在每個循環(huán)中，執(zhí)行循環(huán)替換。
優(yōu)點： 優(yōu)化了循環(huán)替換算法
缺點： 需要計算最大公約數(shù)，復(fù)雜度增加。

復(fù)雜度分析：

解決方案	時間復(fù)雜度	空間復(fù)雜度	原地算法？
暴力法	O(n * k)	O(1)	是
額外數(shù)組	O(n)	O(n)	否
反轉(zhuǎn)數(shù)組	O(n)	O(1)	是
循環(huán)替換	O(n)	O(1)	是
GCD循環(huán)替換	O(n)	O(1)	是

三、算法實現(xiàn)

3.1、使用額外數(shù)組（效果較差）

創(chuàng)建一個新的數(shù)組 new_nums，長度與原數(shù)組相同。
將原數(shù)組 nums 中的后 k % num.size()個元素 nums[i] 放到新數(shù)組的開頭位置上，其他元素依次放在末尾。
將新數(shù)組 new_nums 復(fù)制回原數(shù)組 nums。

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

時間復(fù)雜度：

時間復(fù)雜度較低，為 O(n)。
需要額外的 O(n) 空間。

3.2、反轉(zhuǎn)數(shù)組3次（實現(xiàn)簡單）

這種方法實現(xiàn)相對容易，而且容易理解。

將整個數(shù)組反轉(zhuǎn)。
將數(shù)組的前 k % n 個元素反轉(zhuǎn)。
將數(shù)組的后 n - (k % n) 個元素反轉(zhuǎn)。

原理：

例如 nums = [1, 2, 3, 4, 5, 6, 7], k = 3
反轉(zhuǎn)整個數(shù)組：[7, 6, 5, 4, 3, 2, 1]
反轉(zhuǎn)前 k 個元素：[5, 6, 7, 4, 3, 2, 1]
反轉(zhuǎn)后 n-k 個元素：[5, 6, 7, 1, 2, 3, 4]

代碼實現(xiàn)：

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

3.3、循環(huán)替換（較為復(fù)雜）

從位置 0 開始，將該位置的元素移動到 (0 + k) % n 位置，再將該位置的元素移動到 (0 + 2k) % n 位置，以此類推。

為了避免重復(fù)循環(huán)，需要記錄已經(jīng)訪問過的位置，或者使用一個計數(shù)器來控制循環(huán)的次數(shù)。

可以使用GCD（最大公約數(shù)）來優(yōu)化循環(huán)替換：

如果 n 和 k 的最大公約數(shù)是 1，那么只需要一個循環(huán)就能完成所有的替換。但如果最大公約數(shù)不是1，則需要多個循環(huán)。
找到 n 和 k 的最大公約數(shù) gcd。循環(huán)從 0 到 gcd - 1。在每個循環(huán)中，執(zhí)行循環(huán)替換。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        unsigned n = nums.size();
        int gcd = std::gcd(n, k % n);
        for (int i = 0; i < gcd; ++i) {
            int cur = i;
            int pre = nums[cur];
            do {
                int next = (cur + k) % n;
                std::swap(nums[next], pre);
                cur = next;
            } while (cur != i);
        }
    }
};

四、總結(jié)

C++中數(shù)組輪轉(zhuǎn)問題的五種解決方案：暴力法、額外數(shù)組、反轉(zhuǎn)數(shù)組、循環(huán)替換以及GCD優(yōu)化循環(huán)替換。分析了每種算法的時間和空間復(fù)雜度，并特別關(guān)注了原地算法的實現(xiàn)。通過對比不同方案，展示了如何在時間和空間之間權(quán)衡，最終實現(xiàn)高效且節(jié)省空間的數(shù)組輪轉(zhuǎn)。

其中，反轉(zhuǎn)數(shù)組和GCD優(yōu)化循環(huán)替換是在實際項目中推薦使用的。

以上就是在C++中實現(xiàn)高效的數(shù)組原地輪轉(zhuǎn)的方法總結(jié)的詳細(xì)內(nèi)容，更多關(guān)于C++數(shù)組原地輪轉(zhuǎn)的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: