3379. 轉換數組

思路

按照題目要求模擬就好。

• $nums[i] > 0$ ，找到右邊 $nums[i]$ 的數字，放到 $res[i]$ 上。
• $nums[i] < 0$ ，找到左邊 $nums[i]$ 的數字，放到 $res[i]$ 上。
• $nums[i] = 0$ ，找到當前 $nums[i]$ 的數字，放到 $res[i]$ 上。

這三種情況是一樣的，根據 $nums[i]$ 的數字大小，決定找的方向以及距離。
先不考慮負數，如果是往右 $x$ 位，當這個數字 $x$ 很大的時候，要怎麼快速找到目標位置？

注意到如果 $x$ 是 $n$ 的倍數的話，會回到原先的位置，因此可以透過模 $n$ 的方式，快速找到目標位置。

對於負數的情況，我們知道想要得到正確的模運算結果應該，要先加上 $n$ ，比如 $n = 7$ 時。
$(75-17)\%7=2$，$(75\%7-17\%7\blue{+7})\%7=(5-3\blue{+7})\%7 = 2$ ，需要再模運算之後，再加上一個 $n$。
上面的例子看起來 $+n$ 很廢，這也是特性之一，也就是最後算出正數，那加與不加都沒差。
$(72-18)\%7=54\%7=5$，$(72\%7-18\%7+7)\%m=(2-4+7)\%7=5$。
第二個例子中，相減之後是負數，但是餘數不會有負數，因此要加 $7$ 取補數。

之所以 $+n$ 是為了取補數，不過前提是模的數字絕對值不可以大於 $n$，
否則取到的補數會出錯。因此要事先對數值 $\%n$。

程式碼

1. 模擬

class Solution {
public:
    vector<int> constructTransformedArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        for(int i = 0; i < n; i++) {
            int j;
            if(nums[i] < 0) {
                // 減太多會有很多輪，還會爆炸，要事先 % n
                j = (i + -(abs(nums[i]) % n) + n) % n;
            }
            else {
                j = (i + nums[i]) % n;
            }
            res[i] = nums[j];
        }
        return res;
    }
};

2. 合併正負兩種狀況

class Solution {
public:
    vector<int> constructTransformedArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        for(int i = 0; i < n; i++) {
            int j = ((i + nums[i]) % n + n) % n;
            res[i] = nums[j];
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$