【算法leetcode每日一练】2161. 根据给定数字划分数组_给你一个下标从0开始的整数数组nums

---

---

2161. 根据给定数字划分数组：

给你一个下标从 0 开始的整数数组 nums 和一个整数 pivot 。请你将 nums 重新排列，使得以下条件均成立：

• 所有小于 pivot 的元素都出现在所有大于 pivot 的元素 之前 。
• 所有等于 pivot 的元素都出现在小于和大于 pivot 的元素 中间 。
• 小于 pivot 的元素之间和大于 pivot 的元素之间的 相对顺序 不发生改变。
  • 更正式的，考虑每一对 $p_i$，$p_j$ ，$p_i$ 是初始时位置 i 元素的新位置，$p_j$ 是初始时位置 j 元素的新位置。对于小于 pivot 的元素，如果 i < j 且 nums[i] < pivot 和 nums[j] < pivot 都成立，那么 $p_i$ < $p_j$ 也成立。类似的，对于大于 pivot 的元素，如果 i < j 且 nums[i] > pivot 和 nums[j] > pivot 都成立，那么 $p_i$ < $p_j$ 。

请你返回重新排列 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] ，它们在结果数组中的相对顺序需要保留。
1
2
3
4
5
6
7
8
9
10

样例 2：

输入：
	nums = [-3,4,3,2], pivot = 2
	
输出：
	[-3,2,4,3]
	
解释：
	元素 -3 小于 pivot ，所以在数组的最左边。
	元素 4 和 3 大于 pivot ，所以它们在数组的最右边。
	小于 pivot 的元素的相对位置和大于 pivot 的元素的相对位置分别为 [-3] 和 [4, 3] ，它们在结果数组中的相对顺序需要保留。
1
2
3
4
5
6
7
8
9
10

提示：

• 1 <= nums.length <= $10^5$
• $-10^6$ <= nums[i] <= $10^6$
• 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;
    }
}
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

---

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;
}
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

---

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;
    }
};
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

---

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
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

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
}
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

---

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;
    }
}
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

---

---

原题传送门：https://leetcode-cn.com/problems/partition-array-according-to-given-pivot/

---

非常感谢你阅读本文~
欢迎【

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/765874