2.6力扣每日一题-3379转换数组

3379. 转换数组 - 力扣（LeetCode）

视频讲解：https://t.bilibili.com/1166681192552988677?share_source=pc_native

给你一个整数数组 nums，它表示一个循环数组。请你遵循以下规则创建一个大小 相同 的新数组 result ：

对于每个下标 i（其中 0 <= i < nums.length），独立执行以下操作：

• 如果 nums[i] > 0：从下标 i 开始，向 右 移动 nums[i] 步，在循环数组中落脚的下标对应的值赋给 result[i]。
• 如果 nums[i] < 0：从下标 i 开始，向 左 移动 abs(nums[i]) 步，在循环数组中落脚的下标对应的值赋给 result[i]。
• 如果 nums[i] == 0：将 nums[i] 的值赋给 result[i]。

返回新数组 result。

注意：由于 nums 是循环数组，向右移动超过最后一个元素时将回到开头，向左移动超过第一个元素时将回到末尾。

示例 1：

输入： nums = [3,-2,1,1]

输出： [1,1,1,3]

解释：

• 对于 nums[0] 等于 3，向右移动 3 步到 nums[3]，因此 result[0] 为 1。
• 对于 nums[1] 等于 -2，向左移动 2 步到 nums[3]，因此 result[1] 为 1。
• 对于 nums[2] 等于 1，向右移动 1 步到 nums[3]，因此 result[2] 为 1。
• 对于 nums[3] 等于 1，向右移动 1 步到 nums[0]，因此 result[3] 为 3。

示例 2：

输入： nums = [-1,4,-1]

输出： [-1,-1,4]

解释：

• 对于 nums[0] 等于 -1，向左移动 1 步到 nums[2]，因此 result[0] 为 -1。
• 对于 nums[1] 等于 4，向右移动 4 步到 nums[2]，因此 result[1] 为 -1。
• 对于 nums[2] 等于 -1，向左移动 1 步到 nums[1]，因此 result[2] 为 4。

提示：

• 1 <= nums.length <= 100
• -100 <= nums[i] <= 100

我们先抛开数组下标为非负数这个要求，将nums视为一个向两侧无穷延伸的循环数组。题目说如果nums[i]<0，就向左移动abs(nums[i])位，即左移后的下标为i-abs(nums[i])，即为i+nums[i].

也就是说，无论nums[i]是正或是负，移动后的下标都为i+nums[i]，只不过这个i+nums[i]可能大于等于数组的长度或小于0.例如数组长度为4，那么下标1，5，9和下标-3，-7，-11对应的数值是一样的，在这里我们称其为等价的下标。

简化问题：也就是说，我们要解决的问题是，对于一个长度为m的数组nums来说，我们如何找到与i+nums[i]等价的下标，且该下标对nums来说是有效的？

可见，将x调整为y，只需对m取模，加m，再整体对m取模即可。

Java

class Solution {
    public int[] constructTransformedArray(int[] nums) {
        int m = nums.length;
        int[] res = new int[m];
        for(int i=0;i<m;i++) {
            res[i] = nums[((i + nums[i]) % m + m) % m];
        }
        return res;
    }
}

Go

func constructTransformedArray(nums []int) []int {
    m := len(nums)
    res := make([]int,m)
    for i,v := range nums {
        res[i] = nums[((i + v) % m + m) % m]
    }
    return res
}

C++

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

Python

class Solution:
    def constructTransformedArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        return [nums[(i + v) % n] for i, v in enumerate(nums)]