我是靠谱客的博主 激昂柚子，最近开发中收集的这篇文章主要介绍【算法leetcode每日一练】2161. 根据给定数字划分数组2161. 根据给定数字划分数组：样例 1：样例 2：提示：分析题解原题传送门：https://leetcode-cn.com/problems/partition-array-according-to-given-pivot/，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
文章目录
- 2161. 根据给定数字划分数组：
- 样例 1：
- 样例 2：
- 提示：
- 分析
- 题解
- java
- c
- c++
- python
- go
- rust
- 原题传送门：https://leetcode-cn.com/problems/partition-array-according-to-given-pivot/
2161. 根据给定数字划分数组：
给你一个下标从 0 开始的整数数组 nums 和一个整数 pivot 。请你将 nums 重新排列，使得以下条件均成立：
- 所有小于
pivot的元素都出现在所有大于pivot的元素 之前 。 - 所有等于
pivot的元素都出现在小于和大于pivot的元素 中间 。 - 小于
pivot的元素之间和大于pivot的元素之间的 相对顺序 不发生改变。- 更正式的，考虑每一对
p
i
p_i
pi，
p
j
p_j
pj ，
p
i
p_i
pi 是初始时位置
i元素的新位置， p j p_j pj 是初始时位置j元素的新位置。对于小于pivot的元素，如果i < j且nums[i] < pivot和nums[j] < pivot都成立，那么 p i p_i pi < p j p_j pj 也成立。类似的，对于大于pivot的元素，如果i < j且nums[i] > pivot和nums[j] > pivot都成立，那么 p i p_i pi < p j p_j pj 。
- 更正式的，考虑每一对
p
i
p_i
pi，
p
j
p_j
pj ，
p
i
p_i
pi 是初始时位置
请你返回重新排列 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 <= 1 0 5 10^5 105
- − 1 0 6 -10^6 −106 <= nums[i] <= 1 0 6 10^6 106
pivot等于nums中的一个元素。
分析
- 面对这道算法题目，二当家的陷入了沉思。
- 如果不要求保持 相对顺序 的话，我们大可以直接在原数组中进行交换；二当家的开始开始希望降低空间复杂度，尝试原地交换，由于要保持 相对顺序 ，发现时间复杂度太高，要进行大量移动。
- 无奈，只好开辟新空间，进行2轮遍历，第一轮先分别统计小于，等于，大于给定数字的数量（知道其中任意2个，相当于知道了剩下的一个，因为知道总数），相当于知道了结果中三种情况的启始下标；再进行第二轮遍历，将数字放入结果。
题解
java
class Solution {
public int[] pivotArray(int[] nums, int pivot) {
int lc = 0;
int ec = 0;
for (int n : nums) {
if (n < pivot) {
lc++;
} else if (n == pivot) {
ec++;
}
}
int[] ans = new int[nums.length];
int li = 0;
int ei = lc;
int hi = lc + ec;
for (int n : nums) {
if (n < pivot) {
ans[li++] = n;
} else if (n == pivot) {
ans[ei++] = n;
} else {
ans[hi++] = n;
}
}
return ans;
}
}
c
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* pivotArray(int* nums, int numsSize, int pivot, int* returnSize){
int lc = 0;
int ec = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] < pivot) {
lc++;
} else if (nums[i] == pivot) {
ec++;
}
}
int *ans = malloc(sizeof(int) * numsSize);
*returnSize = numsSize;
int li = 0;
int ei = lc;
int hi = lc + ec;
for (int i = 0; i < numsSize; i++) {
if (nums[i] < pivot) {
ans[li++] = nums[i];
} else if (nums[i] == pivot) {
ans[ei++] = nums[i];
} else {
ans[hi++] = nums[i];
}
}
return ans;
}
c++
class Solution {
public:
vector<int> pivotArray(vector<int>& nums, int pivot) {
int lc = 0;
int ec = 0;
for (int n: nums) {
if (n < pivot) {
lc++;
} else if (n == pivot) {
ec++;
}
}
vector<int> ans(nums.size(), pivot);
int li = 0;
int hi = lc + ec;
for (int n: nums) {
if (n < pivot) {
ans[li++] = n;
} else if (n > pivot) {
ans[hi++] = n;
}
}
return ans;
}
};
python
class Solution:
def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
lc = 0
ec = 0
for n in nums:
if n < pivot:
lc += 1
elif n == pivot:
ec += 1
ans = [pivot] * len(nums)
li = 0
hi = lc + ec
for n in nums:
if n < pivot:
ans[li] = n
li += 1
elif n > pivot:
ans[hi] = n
hi += 1
return ans
go
func pivotArray(nums []int, pivot int) []int {
lc := 0
ec := 0
for _, n := range nums {
if n < pivot {
lc++
} else if n == pivot {
ec++
}
}
ans := make([]int, len(nums))
li := 0
ei := lc
hi := lc + ec
for _, n := range nums {
if n < pivot {
ans[li] = n
li++
} else if n == pivot {
ans[ei] = n
ei++
} else {
ans[hi] = n
hi++
}
}
return ans
}
rust
impl Solution {
pub fn pivot_array(nums: Vec<i32>, pivot: i32) -> Vec<i32> {
let mut lc = 0;
let mut ec = 0;
nums.iter().for_each(|&n| {
if n < pivot {
lc += 1;
} else if n == pivot {
ec += 1;
}
});
let mut ans = vec![pivot; nums.len()];
let mut li = 0;
let mut hi = lc + ec;
nums.iter().for_each(|&n| {
if n < pivot {
ans[li] = n;
li += 1;
} else if n > pivot {
ans[hi] = n;
hi += 1;
}
});
return ans;
}
}
原题传送门：https://leetcode-cn.com/problems/partition-array-according-to-given-pivot/
非常感谢你阅读本文~
欢迎【????点赞】【⭐收藏】【????评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~
最后
以上就是激昂柚子为你收集整理的【算法leetcode每日一练】2161. 根据给定数字划分数组2161. 根据给定数字划分数组：样例 1：样例 2：提示：分析题解原题传送门：https://leetcode-cn.com/problems/partition-array-according-to-given-pivot/的全部内容，希望文章能够帮你解决【算法leetcode每日一练】2161. 根据给定数字划分数组2161. 根据给定数字划分数组：样例 1：样例 2：提示：分析题解原题传送门：https://leetcode-cn.com/problems/partition-array-according-to-given-pivot/所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复