跳转至

3865. Reverse K Subarrays 🔒

题目描述

You are given an integer array nums of length n and an integer k.

You must partition the array into k contiguous subarrays of equal length and reverse each subarray.

It is guaranteed that n is divisible by k.

Return the resulting array after performing the above operation.

 

Example 1:

Input: nums = [1,2,4,3,5,6], k = 3

Output: [2,1,3,4,6,5]

Explanation:

  • The array is partitioned into k = 3 subarrays: [1, 2], [4, 3], and [5, 6].
  • After reversing each subarray: [2, 1], [3, 4], and [6, 5].
  • Combining them gives the final array [2, 1, 3, 4, 6, 5].

Example 2:

Input: nums = [5,4,4,2], k = 1

Output: [2,4,4,5]

Explanation:

  • The array is partitioned into k = 1 subarray: [5, 4, 4, 2].
  • Reversing it produces [2, 4, 4, 5], which is the final array.

 

Constraints:

  • 1 <= n == nums.length <= 1000
  • 1 <= nums[i] <= 1000
  • 1 <= k <= n
  • n is divisible by 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
    }
}

评论