LeetCode 2161. Partition Array According to Given Pivot(2025/3/3每日一题）

就很奇怪，最近的每日一题怎么都是序列题。

标题：2161. Partition Array According to Given Pivot

题目：You are given a 0-indexed integer array nums and an integer pivot. Rearrange nums such that the following conditions are satisfied:

• Every element less than pivot appears before every element greater than pivot.
• Every element equal to pivot appears in between the elements less than and greater than pivot.
• The relative order of the elements less than pivot and the elements greater than pivot is maintained.
  • More formally, consider every pi, pj where pi is the new position of the ith element and pj is the new position of the jth element. If i < j and both elements are smaller (or larger) than pivot, then pi < pj.

Return nums after the rearrangement.

例：

Example 1:

Input: nums = [9,12,5,10,14,3,10], pivot = 10
Output: [9,5,3,10,10,12,14]
Explanation: 
The elements 9, 5, and 3 are less than the pivot so they are on the left side of the array.
The elements 12 and 14 are greater than the pivot so they are on the right side of the array.
The relative ordering of the elements less than and greater than pivot is also maintained. [9, 5, 3] and [12, 14] are the respective orderings.

Example 2:

Input: nums = [-3,4,3,2], pivot = 2
Output: [-3,2,4,3]
Explanation: 
The element -3 is less than the pivot so it is on the left side of the array.
The elements 4 and 3 are greater than the pivot so they are on the right side of the array.
The relative ordering of the elements less than and greater than pivot is also maintained. [-3] and [4, 3] are the respective orderings.

Constraints:

• 1 <= nums.length <= 105
• -106 <= nums[i] <= 106
• pivot equals to an element of nums.

解题思路：这题用O(N)存储空间的解题方法不难。声明一个与给定数组同等大小的数组，用两个指针一个指向数组最前端，用于填充小于pivot的元素，一个指向数组最后端，用于填充大于pivot的元素。最后两个指针中间的部分就是等于pivot的元素。这里有个小trick：在筛选小于pivot元素时，由于需要保持相对位置不变，需要正向遍历整个数组；筛选大于pivot元素时，也需要保持相对位置不变，需要反向遍历整个数组。加起来是需要遍历两次。可以用正向索引i,计算出反向索引(size-1-i)，正向反向同时遍历，可以只遍历一次，时间复杂度减小一半。代码如下：

class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        vector<int> ans(nums.size(), 0);
        int start = 0, end = nums.size()-1;
        for(int i = 0; i < nums.size(); i++){
            if (nums[i] < pivot) ans[start++] = nums[i];
            if (nums[nums.size()-1-i] > pivot) ans[end--] = nums[nums.size()-1-i];
        }
        while(start <= end) ans[start++] = pivot;
        return ans;
    }
};

时间复杂度O(N)。空间复杂度O(N).

还有in-place解法，等有空更新