Medium

题目描述

给你一个整数数组 nums 和一个整数 k。

将数组中所有非负元素按循环方式向左旋转 k 个位置。

所有负元素必须保持在其原始位置，不得移动。

旋转后，将非负元素按新的顺序放回数组中，只填充原来包含非负值的位置，跳过所有负数位置。

返回结果数组。

示例 1：

输入：nums = [1,-2,3,-4], k = 3
输出：[3,-2,1,-4]
解释：
非负元素按顺序为 [1, 3]。
左旋转 k = 3 的结果：
[1, 3] -> [3, 1] -> [1, 3] -> [3, 1]
将它们放回非负索引位置得到 [3, -2, 1, -4]。

示例 2：

输入：nums = [-3,-2,7], k = 1
输出：[-3,-2,7]
解释：
非负元素按顺序为 [7]。
左旋转 k = 1 的结果为 [7]。
将它们放回非负索引位置得到 [-3, -2, 7]。

示例 3：

输入：nums = [5,4,-9,6], k = 2
输出：[6,5,-9,4]
解释：
非负元素按顺序为 [5, 4, 6]。
左旋转 k = 2 的结果为 [6, 5, 4]。
将它们放回非负索引位置得到 [6, 5, -9, 4]。

约束条件：

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

解题思路

这道题的核心思路是将非负元素提取出来，进行旋转操作，然后放回原位置。

算法步骤：

  1. 提取非负元素：遍历数组，找出所有非负元素及其位置索引
  2. 旋转操作：对提取的非负元素数组执行左旋转k位操作。由于是循环旋转，可以使用 k % 非负元素个数 来优化
  3. 放回原位：将旋转后的非负元素按顺序放回到原来非负元素的位置上

旋转实现方式：

  • 方法1：使用额外数组存储旋转结果
  • 方法2：使用数组切片拼接（Python特有）
  • 方法3：使用反转算法（最优空间复杂度）

优化要点：

  • 当k大于非负元素个数时，使用取模运算避免无效旋转
  • 如果没有非负元素，直接返回原数组
  • 负数元素位置保持不变

这种方法时间复杂度为O(n)，空间复杂度为O(m)，其中m是非负元素的个数。

代码实现

class Solution {
public:
    vector<int> rotateElements(vector<int>& nums, int k) {
        vector<int> nonNegative;
        vector<int> indices;
        
        // 提取非负元素及其索引
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] >= 0) {
                nonNegative.push_back(nums[i]);
                indices.push_back(i);
            }
        }
        
        // 如果没有非负元素，直接返回
        if (nonNegative.empty()) {
            return nums;
        }
        
        // 优化k值
        k = k % nonNegative.size();
        
        // 执行左旋转
        vector<int> rotated;
        for (int i = k; i < nonNegative.size(); i++) {
            rotated.push_back(nonNegative[i]);
        }
        for (int i = 0; i < k; i++) {
            rotated.push_back(nonNegative[i]);
        }
        
        // 放回原位置
        for (int i = 0; i < indices.size(); i++) {
            nums[indices[i]] = rotated[i];
        }
        
        return nums;
    }
};

class Solution:
    def rotateElements(self, nums: List[int], k: int) -> List[int]:
        # 提取非负元素及其索引
        non_negative = []
        indices = []
        
        for i, num in enumerate(nums):
            if num >= 0:
                non_negative.append(num)
                indices.append(i)
        
        # 如果没有非负元素，直接返回
        if not non_negative:
            return nums
        
        # 优化k值并执行左旋转
        k = k % len(non_negative)
        rotated = non_negative[k:] + non_negative[:k]
        
        # 放回原位置
        for i, idx in enumerate(indices):
            nums[idx] = rotated[i]
        
        return nums

public class Solution {
    public int[] RotateElements(int[] nums, int k) {
        var nonNegative = new List<int>();
        var indices = new List<int>();
        
        // 提取非负元素及其索引
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] >= 0) {
                nonNegative.Add(nums[i]);
                indices.Add(i);
            }
        }
        
        // 如果没有非负元素，直接返回
        if (nonNegative.Count == 0) {
            return nums;
        }
        
        // 优化k值
        k = k % nonNegative.Count;
        
        // 执行左旋转
        var rotated = new List<int>();
        for (int i = k; i < nonNegative.Count; i++) {
            rotated.Add(nonNegative[i]);
        }
        for (int i = 0; i < k; i++) {
            rotated.Add(nonNegative[i]);
        }
        
        // 放回原位置
        for (int i = 0; i < indices.Count; i++) {
            nums[indices[i]] = rotated[i];
        }
        
        return nums;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var rotateElements = function(nums, k) {
    const nonNegative = [];
    const nonNegativeIndices = [];
    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] >= 0) {
            nonNegative.push(nums[i]);
            nonNegativeIndices.push(i);
        }
    }
    
    if (nonNegative.length === 0) return nums;
    
    const actualK = k % nonNegative.length;
    const rotated = [...nonNegative.slice(actualK), ...nonNegative.slice(0, actualK)];
    
    const result = [...nums];
    for (let i = 0; i < nonNegativeIndices.length; i++) {
        result[nonNegativeIndices[i]] = rotated[i];
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
提取非负元素O(n)O(m)
旋转操作O(m)O(m)
放回原位置O(m)O(1)
总计O(n)O(m)

其中 n 是数组长度，m 是非负元素的个数 (m ≤ n)