宁夏建设工程交易中心网站,记事本做网站怎么插图,网站收录在哪里可以查看,手机优化助手怎么样给你一个下标从 0 开始的整数数组 nums 和一个整数 pivot 。请你将 nums 重新排列#xff0c;使得以下条件均成立#xff1a;
所有小于 pivot 的元素都出现在所有大于 pivot 的元素 之前 。 所有等于 pivot 的元素都出现在小于和大于 pivot 的元素 中间 。 小于 pivot 的元素…给你一个下标从 0 开始的整数数组 nums 和一个整数 pivot 。请你将 nums 重新排列使得以下条件均成立
所有小于 pivot 的元素都出现在所有大于 pivot 的元素 之前 。 所有等于 pivot 的元素都出现在小于和大于 pivot 的元素 中间 。 小于 pivot 的元素之间和大于 pivot 的元素之间的 相对顺序 不发生改变。 更正式的考虑每一对 pipj pi 是初始时位置 i 元素的新位置pj 是初始时位置 j 元素的新位置。对于小于 pivot 的元素如果 i j 且 nums[i] pivot 和 nums[j] pivot 都成立那么 pi pj 也成立。类似的对于大于 pivot 的元素如果 i j 且 nums[i] pivot 和 nums[j] pivot 都成立那么 pi pj 。 请你返回重新排列 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 105 -106 nums[i] 106 pivot 等于 nums 中的一个元素。
法一按顺序保存下来小于pivot和大于pivot的数再拼接
class Solution {
public:vectorint pivotArray(vectorint nums, int pivot) {vectorint small;vectorint big;int pivotNum 0;for (int num : nums){if (num pivot){small.push_back(num);}else if (num pivot){big.push_back(num);}else{pivotNum;}}for (int i 0; i pivotNum; i){small.push_back(pivot);}small.insert(small.end(), big.begin(), big.end());return small;}
};如果nums的长度为n此算法时间复杂度为O(n)空间复杂度为O(n)。
法二直接在结果数组中构建答案先正向遍历nums把小于pivot的数按顺序放在左边然后反向遍历nums把大于pivot的数按顺序放在右边中间填充pivot即可
class Solution {
public:vectorint pivotArray(vectorint nums, int pivot) {vectorint ans(nums.size());int smallIndex 0;for (int num : nums){if (num pivot){ans[smallIndex] num;}}int bigIndex nums.size() - 1;for (vectorint::reverse_iterator it nums.rbegin(); it ! nums.rend(); it){if (*it pivot){ans[bigIndex--] *it;}}while (smallIndex bigIndex){ans[smallIndex] pivot;ans[bigIndex--] pivot;}return ans;}
};如果nums的长度为n此算法时间复杂度为O(n)空间复杂度为O(1)。本解法也可以一遍正向遍历把大于pivot的值在ans的最后从右往左排最后再reverse一下大于pivot的值即可
class Solution {
public:vectorint pivotArray(vectorint nums, int pivot) {vectorint ans(nums.size(), pivot);int smallIndex 0;int bigIndex nums.size() - 1;for (int num : nums){if (num pivot){ans[smallIndex] num;}else if (num pivot){ans[bigIndex--] num;}}reverse(ans.begin() bigIndex 1, ans.end());return ans;}
};
