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
pivotappears before every element greater thanpivot. - Every element equal to
pivotappears in between the elements less than and greater thanpivot. - The relative order of the elements less than
pivotand the elements greater thanpivotis maintained. - More formally, consider every
pi,pjwherepiis the new position of thei^thelement andpjis the new position of thej^thelement. Ifi < jand both elements are smaller (or larger) thanpivot, thenpi < pj.
Return nums after the rearrangement.
Example 1
Input
nums = [9,12,5,10,14,3,10], pivot = 10Output
[9,5,3,10,10,12,14]The elements 9, 5, and 3 are less than the pivot, the elements 12 and 14 are greater than the pivot, and the relative orderings [9, 5, 3] and [12, 14] are maintained.
Example 2
Input
nums = [-3,4,3,2], pivot = 2Output
[-3,2,4,3]The element -3 is less than the pivot, the elements 4 and 3 are greater than the pivot, and the relative orderings [-3] and [4, 3] are maintained.
Constraints
- 1 <= nums.length <= 10^5
- -10^6 <= nums[i] <= 10^6
- pivot equals to an element of nums.