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 thanpivot
. - Every element equal to
pivot
appears in between the elements less than and greater thanpivot
. - The relative order of the elements less than
pivot
and the elements greater thanpivot
is maintained.- More formally, consider every
pi
,pj
wherepi
is the new position of theith
element andpj
is the new position of thejth
element. For elements less thanpivot
, ifi < j
andnums[i] < pivot
andnums[j] < pivot
, thenpi < pj
. Similarly for elements greater thanpivot
, ifi < j
andnums[i] > pivot
andnums[j] > pivot
, thenpi < pj
.
- More formally, consider every
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 ofnums
.
Similar Questions:
This problem looks similar to the partitioning process in Quick Sort, but since the efficient partition algorithms (Lomuto's and Hoare's) are not stable, you can't use it here.
// OJ: https://leetcode.com/problems/partition-array-according-to-given-pivot/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<int> pivotArray(vector<int>& A, int pivot) {
vector<int> gt; // numbers greater than pivot
int j = 0, cnt = 0; // `j` is the write pointer. `cnt` is the count of numbers equal to pivot
for (int i = 0; i < A.size(); ++i) {
if (A[i] < pivot) A[j++] = A[i];
else if (A[i] == pivot) ++cnt;
else gt.push_back(A[i]);
}
while (cnt--) A[j++] = pivot;
for (int i = 0; i < gt.size(); ++i) A[j++] = gt[i];
return A;
}
};
https://leetcode.com/problems/partition-array-according-to-given-pivot/discuss/1746999
The above post was hidden for no reason...
https://leetcode.com/problems/partition-array-according-to-given-pivot/discuss/1747363