我是靠谱客的博主 友好黄蜂，这篇文章主要介绍【算法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：
复制代码
1
2
3
4
5
6
7
8
9
10
11输入： 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：
复制代码
1
2
3
4
5
6
7
8
9
10
11输入： 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
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class 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
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32/** * 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++
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class 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
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class 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
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31func 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
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29impl 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.内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复