Q2. Rotate Non-Negative Elements

📘 題目敘述

給你一個整數陣列 nums 與一個整數 k。

請你只針對陣列中的「非負數元素（>= 0）」做旋轉操作：把這些非負數元素向左循環旋轉 k 個位置。

同時必須滿足：

• 所有負數元素都必須保持在原本的位置，不能移動
• 旋轉後，把非負數元素依照新順序放回陣列中，只填回原本是非負數的位置，遇到負數位置要跳過

最後回傳旋轉後的陣列。

條件限制

• 1 <= nums.length <= 10^5
• -10^5 <= nums[i] <= 10^5
• 0 <= k <= 10^5

🧠 解題思路

我的想法是把「負數位置完全不動」這件事拆開處理：我先把所有非負數抽出來，單獨做旋轉，最後再放回去原本那些非負數的位置。

這樣做的好處是：

• 負數不用管，因為我根本不會去改它們的位置
• 我只在「原本非負數的位置」寫回新順序的數字

所有變數

• n：nums 的長度
• spos：所有「非負數的位置索引」(positions)
• snum：依照出現順序收集到的「非負數值」(numbers)
• m：非負數的總數（也就是 spos.size()）
• k：要向左旋轉的步數（用 % m 做循環）

🪜 主要流程步驟

1. 先掃過整個陣列，把非負數抽出來

• 如果 nums[i] >= 0：
  • 把索引 i 存進 spos
  • 把數值 nums[i] 存進 snum

這一步做完後：

• spos[j] 代表第 j 個非負數原本在 nums 的哪個位置
• snum[j] 代表第 j 個非負數的值

2. 將非負數做「向左旋轉 k」

「向左旋轉」的意思是：原本第 j 個非負數，旋轉後會變成放到第 j - k 的位置（循環）。

我在寫回去的時候，用的是等價的索引轉換：

• 對每個非負數位置 spos[j]（也就是要填回去的第 j 個槽位）
• 填入旋轉後該出現的值：snum[(j + k) % m]

這樣就完成了循環左旋（因為只在非負數序列內部重新排列）。

3. 把旋轉後的非負數放回原陣列

• 只寫回 nums[spos[j]]
• 負數的位置根本不在 spos 裡，所以自然不會被改到

💻 程式碼實作

class Solution {
public:
    vector<int> rotateElements(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> spos;
        vector<int> snum;
        for (int i = 0; i < n; i++) {
            if (nums[i] >= 0) {
                spos.push_back(i);
                snum.push_back(nums[i]);
            }
        }
        int m = spos.size();
        for (int j = 0; j < m; j++) {
            nums[spos[j]] = snum[(j + k) % m];
        }
        return nums;
    }
};

🔗 題目連結

https://leetcode.com/contest/weekly-contest-486/problems/rotate-non-negative-elements/