跳转至

3865. 反转 K 个子数组 🔒

题目描述

给定一个长度为 n 的整数数组 nums 和一个整数 k。

你必须将数组 划分 为 k 个长度 相等 的连续子数组，并 反转 每个子数组。

保证 n 能被 k 整除。

返回上述操作后的结果数组。

 

示例 1：

输入：nums = [1,2,4,3,5,6], k = 3

输出：[2,1,3,4,6,5]

解释：

  • 数组被划分为 k = 3 个子数组：[1, 2]，[4, 3]，和 [5, 6]。
  • 反转每个子数组后：[2, 1]，[3, 4]，和 [6, 5]。
  • 组合它们得到最终数组 [2, 1, 3, 4, 6, 5]。

示例 2：

输入：nums = [5,4,4,2], k = 1

输出：[2,4,4,5]

解释：

  • 数组被划分为 k = 1 个子数组：[5, 4, 4, 2]。
  • 反转它得到 [2, 4, 4, 5]，即最终数组。

 

提示：

  • 1 <= n == nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • 1 <= k <= n
  • n 能被 k 整除。

解法

方法一：模拟

由于需要将数组分成 \(k\) 个长度相等的子数组，因此每个子数组的长度为 \(m = \frac{n}{k}\)。我们可以使用一个循环，按照步长 \(m\) 遍历数组，并在每次迭代中将当前子数组进行反转。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(\textit{nums}\) 的长度。空间复杂度 \(O(1)\)，我们只使用了常数级别的额外空间。

1
2
3
4
5
6
7
class Solution:
    def reverseSubarrays(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        m = n // k
        for i in range(0, n, m):
            nums[i : i + m] = nums[i : i + m][::-1]
        return nums

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int[] reverseSubarrays(int[] nums, int k) {
        int n = nums.length;
        int m = n / k;
        for (int i = 0; i < n; i += m) {
            int l = i, r = i + m - 1;
            while (l < r) {
                int t = nums[l];
                nums[l++] = nums[r];
                nums[r--] = t;
            }
        }
        return nums;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    vector<int> reverseSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        int m = n / k;
        for (int i = 0; i < n; i += m) {
            int l = i, r = i + m - 1;
            while (l < r) {
                swap(nums[l++], nums[r--]);
            }
        }
        return nums;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func reverseSubarrays(nums []int, k int) []int {
    n := len(nums)
    m := n / k
    for i := 0; i < n; i += m {
        l, r := i, i+m-1
        for l < r {
            nums[l], nums[r] = nums[r], nums[l]
            l++
            r--
        }
    }
    return nums
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function reverseSubarrays(nums: number[], k: number): number[] {
    const n = nums.length;
    const m = Math.floor(n / k);
    for (let i = 0; i < n; i += m) {
        let l = i,
            r = i + m - 1;
        while (l < r) {
            const t = nums[l];
            nums[l++] = nums[r];
            nums[r--] = t;
        }
    }
    return nums;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
impl Solution {
    pub fn reverse_subarrays(mut nums: Vec<i32>, k: i32) -> Vec<i32> {
        let n = nums.len();
        let m = n / k as usize;

        for i in (0..n).step_by(m) {
            let mut l = i;
            let mut r = i + m - 1;
            while l < r {
                nums.swap(l, r);
                l += 1;
                r -= 1;
            }
        }

        nums
    }
}

评论