当前位置：首页 > news >正文

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

news 2026/6/9 1:43:08

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

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

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

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

请你返回重新排列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 <= 10⁵
-10⁶<= nums[i] <= 10⁶
pivot等于nums中的一个元素。

解题方法：双指针

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

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

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

时间复杂度O ( l e n ( n u m s ) ) O(len(nums))O(len(nums))
空间复杂度O ( 1 ) O(1)O(1)

AC代码

C++

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