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

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

示例：

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

要求：

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

提示：

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

二、問題分析

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

關鍵點：

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

思路 1： 暴力法（重復移動）。

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

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

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

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

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

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

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

復雜度分析：

三、算法實現(xiàn)

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

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

時間復雜度：

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

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

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

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

原理：

• 例如 nums = [1, 2, 3, 4, 5, 6, 7], k = 3
• 反轉整個數(shù)組：[7, 6, 5, 4, 3, 2, 1]
• 反轉前 k 個元素：[5, 6, 7, 4, 3, 2, 1]
• 反轉后 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)替換（較為復雜）

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

為了避免重復循環(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);
        }
    }
};

四、總結

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

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

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

最新評論