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

🟠   🔖  数组 双指针 模拟  🔗 力扣 LeetCode

题目

You are given a 0-indexed integer array nums and an integer pivot. Rearrange nums such that the following conditions are satisfied:

• Every element less than pivot appears before every element greater than pivot.
• Every element equal to pivot appears in between the elements less than and greater than pivot.
• The relative order of the elements less than pivot and the elements greater than pivot is maintained.

  • More formally, consider every pi, pj where pi is the new position of the ith element and pj is the new position of the jth element. For elements less than pivot, if i < j and nums[i] < pivot and nums[j] < pivot, then pi < pj. Similarly for elements greater than pivot, if i < j and nums[i] > pivot and nums[j] > pivot, then pi < pj.

Return nums after the rearrangement.

Example 1:

Input: nums = [9,12,5,10,14,3,10], pivot = 10

Output: [9,5,3,10,10,12,14]

Explanation:

The elements 9, 5, and 3 are less than the pivot so they are on the left side of the array.

The elements 12 and 14 are greater than the pivot so they are on the right side of the array.

The relative ordering of the elements less than and greater than pivot is also maintained. [9, 5, 3] and [12, 14] are the respective orderings.

Example 2:

Input: nums = [-3,4,3,2], pivot = 2

Output: [-3,2,4,3]

Explanation:

The element -3 is less than the pivot so it is on the left side of the array.

The elements 4 and 3 are greater than the pivot so they are on the right side of the array.

The relative ordering of the elements less than and greater than pivot is also maintained. [-3] and [4, 3] are the respective orderings.

Constraints:

• 1 <= nums.length <= 10^5
• -10^6 <= nums[i] <= 10^6
• pivot equals to an element of nums.

题目大意

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

• 所有小于 pivot 的元素都出现在所有大于 pivot 的元素 之前 。
• 所有等于 pivot 的元素都出现在小于和大于 pivot 的元素 中间 。
• 小于 pivot 的元素之间和大于 pivot 的元素之间的 相对顺序 不发生改变。

  • 更正式的，考虑每一对 pi，pj ，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 <= 10^5
• -10^6 <= nums[i] <= 10^6
• pivot 等于 nums 中的一个元素。

解题思路

思路一：三路分区

这类 稳定排序 问题适合 三路分区（Three-way partitioning），即：

1. 维护 三个列表：
   • less：存放 小于 pivot 的元素。
   • same：存放 等于 pivot 的元素。
   • greater：存放 大于 pivot 的元素。
2. 遍历 nums，根据 num 的大小，放入对应的列表。
3. 最终 按顺序拼接：less + same + greater。

复杂度分析

• 时间复杂度：O(n)，遍历数组一次，拼接 O(n)。
• 空间复杂度：O(n)，使用了额外的数组存储分类数据。

---

思路二：双指针

1. 第一遍遍历：统计 pivot 出现的次数 sameCount，并计算 小于 pivot 的元素的数量，用 lessCount 记录。
2. 第二遍遍历：
   • 前 lessCount 位置填充 小于 pivot 的元素。
   • 接下来 sameCount 个位置填充 pivot。
   • 最后填充 大于 pivot 的元素。

复杂度分析

• 时间复杂度：O(n)，遍历数组两次。
• 空间复杂度：O(n)，O(1) 额外空间，避免了 less/same/greater 额外数组，更节省内存。

代码

三路分区

/**
 * @param {number[]} nums
 * @param {number} pivot
 * @return {number[]}
 */
var pivotArray = function (nums, pivot) {
	let less = [],
		same = [],
		greater = [];
	for (let num of nums) {
		if (num < pivot) {
			less.push(num);
		} else if (num > pivot) {
			greater.push(num);
		} else {
			same.push(num);
		}
	}
	return less.concat(same, greater);
};

双指针

/**
 * @param {number[]} nums
 * @param {number} pivot
 * @return {number[]}
 */
var pivotArray = function (nums, pivot) {
	let result = [];
	let sameCount = 0;
	let lessCount = 0;

	// 计算 pivot 出现的次数，并填充小于 pivot 的数
	for (let num of nums) {
		if (num < pivot) {
			result.push(num);
			lessCount++;
		} else if (num == pivot) {
			sameCount++;
		}
	}
	// 填充 pivot
	while (sameCount > 0) {
		result.push(pivot);
		sameCount--;
	}
	// 填充大于 pivot 的数
	for (let num of nums) {
		if (num > pivot) {
			result.push(num);
		}
	}
	return result;
};

相关题目

题号	标题	题解	标签	难度	力扣
86	分隔链表	[✓]	链表 双指针	🟠	🀄️ 🔗
2149	按符号重排数组		数组 双指针 模拟	🟠	🀄️ 🔗