2161.根据给定数字划分数组：双指针（O(1)但非源地操作）

【LetMeFly】2161.根据给定数字划分数组：双指针（O(1)但非源地操作）

力扣题目链接：https://leetcode.cn/problems/partition-array-according-to-given-pivot/

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

• 所有小于 pivot 的元素都出现在所有大于 pivot 的元素 之前 。
• 所有等于 pivot 的元素都出现在小于和大于 pivot 的元素 中间 。
• 小于 pivot 的元素之间和大于 pivot 的元素之间的 相对顺序 不发生改变。
  • 更正式的，考虑每一对 pi，pj ，pi 是初始时位置 i 元素的新位置，pj 是初始时位置 j 元素的新位置。如果 i < j 且两个元素 都 小于（或大于）pivot，那么 pi < pj 。

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

 

示例 1：

输入：nums = [9,12,5,10,14,3,10], pivot = 10
输出：[9,5,3,10,10,12,14]
解释：
元素 9 ，5 和 3 小于 pivot ，所以它们在数组的最左边。
元素 12 和 14 大于 pivot ，所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [9, 5, 3] 和 [12, 14] ，它们在结果数组中的相对顺序需要保留。

示例 2：

输入：nums = [-3,4,3,2], pivot = 2
输出：[-3,2,4,3]
解释：
元素 -3 小于 pivot ，所以在数组的最左边。
元素 4 和 3 大于 pivot ，所以它们在数组的最右边。
小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [-3] 和 [4, 3] ，它们在结果数组中的相对顺序需要保留。

 

提示：

• 1 <= nums.length <= 105
• -106 <= nums[i] <= 106
• pivot 等于 nums 中的一个元素。

解题方法：双指针

首先需要明确的是，这道题暂时没有找到合适的原地操作的方法。所谓空间复杂度$O(1)$，实则是因为力扣返回值不计入算法空间复杂度。

开辟一个和原始数组等长的答案数组，使用两个指针分别从左往右存放比$pivot$小的值和从右往左存放比$pivot$大的值。

最后记得把比$pivot$大的部分reverse一下（因为我们是优先把比$pivot$大的值放到最后面了所以需要翻转一下），中间没有填的位置默认赋值为$pivot$。

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-06-08 20:34:51
 */
class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        int n = nums.size();
        vector<int> ans(n, pivot);
        int l = 0, r = n - 1;
        for (int i = 0; i < n; i++) {
            if (nums[i] < pivot) {
                ans[l++] = nums[i];
            } else if (nums[i] > pivot) {
                ans[r--] = nums[i];
            }
        }
        reverse(ans.begin() + r + 1, ans.end());
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源