2161: Partition-Array-According-to-Given-Pivot
Medium
table of contents
Initially, I went for a 3 pointer approach;
just count the number of elements that is smaller than
the pivot, l
, and elements that are equal
to the pivot, s
. The 3 pointers we are initializing are
left = 0
, middle = l
and
right = l + s
.
Then, after initializing an ans
array, we can re-iterate
through nums
and:
code
class Solution {
public:
<int> pivotArray(vector<int>& nums, int pivot) {
vectorint l = 0;
int s = 0;
for (int n : nums) {
if (n < pivot) {
++l;
} else if (n == pivot) {
++s;
}
}
int l_index = 0;
int s_index = l;
int m_index = l+s;
<int> new_nums(nums.size());
vectorfor (int n : nums) {
if (n < pivot) {
[l_index] = n;
new_nums++;
l_index} else if (n == pivot) {
[s_index] = n;
new_numss_index++;
} else {
[m_index] = n;
new_numsm_index++;
}
}
return new_nums;
}
};
However, the above solution requires 2 traversals of
nums
.
In fact, we can shorten it down by simultaneously iterating from both
sides at the same time. Initializing an ans
array, and
keeping track of 2 variables start
and end
, we
know that:
Then, the remaining elements between index start
and
end
must be equal to pivot
.
code
class Solution {
public:
<int> pivotArray(vector<int>& nums, int pivot) {
vectorint beginning = 0;
int ending = nums.size()-1;
<int> ans(nums.size());
vectorfor (int i = 0, j = nums.size()-1; i < nums.size(), j >= 0; ++i, --j) {
if (nums[i] < pivot) {
[beginning] = nums[i];
ans++beginning;
}
if (nums[j] > pivot) {
[ending] = nums[j];
ans--ending;
}
}
while(beginning <= ending) {
[beginning++] = pivot;
ans}
return ans;
}
};