Medium

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个整数 pivot 。请你将 nums 重新排列，使其满足以下条件：

  • 所有小于 pivot 的元素都出现在所有大于 pivot 的元素之前。
  • 所有等于 pivot 的元素都出现在小于和大于 pivot 的元素中间。
  • 小于 pivot 的元素之间和大于 pivot 的元素之间的相对顺序不变。
    • 更正式的，考虑每一对 pi，pj，其中 pi 是第 i 个元素的新位置，pj 是第 j 个元素的新位置。对于小于 pivot 的元素，如果 i < j 且 nums[i] < pivot 和 nums[j] < pivot 都成立，那么 pi < pj 也成立。对于大于 pivot 的元素也有类似的规则。

请你返回重新排列 nums 数组后的结果。

示例 1：

输入：nums = [9,12,5,10,14,3,10], pivot = 10
输出：[9,5,3,10,10,12,14]
解释：
元素 9，5，和 3 小于基准值，所以它们在数组的左边。
元素 12 和 14 大于基准值，所以它们在数组的右边。
小于和大于基准值的元素的相对顺序也保持不变。[9, 5, 3] 和 [12, 14] 是它们各自的顺序。

示例 2：

输入：nums = [-3,4,3,2], pivot = 2
输出：[-3,2,4,3]
解释：
元素 -3 小于基准值，所以它在数组的左边。
元素 4 和 3 大于基准值，所以它们在数组的右边。
小于和大于基准值的元素的相对顺序也保持不变。[-3] 和 [4, 3] 是它们各自的顺序。

提示：

  • 1 <= nums.length <= 10^5
  • -10^6 <= nums[i] <= 10^6
  • pivot 等于 nums 中的一个元素。

解题思路

这道题要求我们根据基准值 pivot 对数组进行分割重排，同时保持相对顺序。

解题思路

方法一：三次遍历（推荐） 最直观的思路是分三步处理：

  1. 第一次遍历：收集所有小于 pivot 的元素
  2. 第二次遍历：收集所有等于 pivot 的元素
  3. 第三次遍历：收集所有大于 pivot 的元素

这样可以确保：

  • 小于 pivot 的元素在最前面
  • 等于 pivot 的元素在中间
  • 大于 pivot 的元素在最后面
  • 由于我们按原数组顺序遍历，自然保持了相对顺序

方法二：一次遍历优化 我们也可以用一次遍历，同时维护三个列表分别存储小于、等于、大于基准值的元素，最后拼接。

时间复杂度都是 O(n)，空间复杂度 O(n)。由于题目要求保持相对顺序且要重新排列，额外空间是必需的。

两种方法在实际性能上差异不大，第一种方法代码更清晰易懂。

代码实现

class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        vector<int> result;
        
        // 第一次遍历：添加所有小于pivot的元素
        for (int num : nums) {
            if (num < pivot) {
                result.push_back(num);
            }
        }
        
        // 第二次遍历：添加所有等于pivot的元素
        for (int num : nums) {
            if (num == pivot) {
                result.push_back(num);
            }
        }
        
        // 第三次遍历：添加所有大于pivot的元素
        for (int num : nums) {
            if (num > pivot) {
                result.push_back(num);
            }
        }
        
        return result;
    }
};

class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        result = []
        
        # 第一次遍历：添加所有小于pivot的元素
        for num in nums:
            if num < pivot:
                result.append(num)
        
        # 第二次遍历：添加所有等于pivot的元素
        for num in nums:
            if num == pivot:
                result.append(num)
        
        # 第三次遍历：添加所有大于pivot的元素
        for num in nums:
            if num > pivot:
                result.append(num)
        
        return result

public class Solution {
    public int[] PivotArray(int[] nums, int pivot) {
        List<int> result = new List<int>();
        
        // 第一次遍历：添加所有小于pivot的元素
        foreach (int num in nums) {
            if (num < pivot) {
                result.Add(num);
            }
        }
        
        // 第二次遍历：添加所有等于pivot的元素
        foreach (int num in nums) {
            if (num == pivot) {
                result.Add(num);
            }
        }
        
        // 第三次遍历：添加所有大于pivot的元素
        foreach (int num in nums) {
            if (num > pivot) {
                result.Add(num);
            }
        }
        
        return result.ToArray();
    }
}

/**
 * @param {number[]} nums
 * @param {number} pivot
 * @return {number[]}
 */
var pivotArray = function(nums, pivot) {
    let less = [];
    let equal = [];
    let greater = [];
    
    for (let num of nums) {
        if (num < pivot) {
            less.push(num);
        } else if (num === pivot) {
            equal.push(num);
        } else {
            greater.push(num);
        }
    }
    
    return [...less, ...equal, ...greater];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组三次，每次 O(n)
空间复杂度O(n)需要额外的结果数组存储重排后的元素

相关题目