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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:26 2023-09-13 16:06:26 Updated    

给你一个下标从 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 <= 105
  • -106 <= nums[i] <= 106
  • pivot 等于 nums 中的一个元素。

方法一：双指针

思路与算法

我们可以对数组 nums 进行一次遍历，并使用两个指针 left 和 right 来更新答案数组。答案数组长度与 nums 的长度相同，初始时，left 和 right 分别指向答案数组的最左端和最右端。

在对 nums 进行遍历时，记当前遍历到的数为 x。如果 x < \textit{pivot，我们就将 x 放入左指针的位置，并将左指针向右移动一个位置；如果 x > \textit{pivot，我们就将 x 放入右指针的位置，并将右指针向左移动一个位置。

在遍历结束之后，我们需要注意两点：

  • 对于所有与 pivot 相等的元素，我们并没有进行处理。我们可以在初始化答案数组时，直接将所有元素赋值为 pivot 来避免额外的处理；

  • 对于严格大于 pivot 的元素，题目中要求它们的「相对顺序」不能发生改变，因此需要将这些元素在答案数组中对应的段进行反转。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        int n = nums.size();
        vector<int> ans(n, pivot);
        int left = 0, right = n - 1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] < pivot) {
                ans[left] = nums[i];
                ++left;
            }
            else if (nums[i] > pivot) {
                ans[right] = nums[i];
                --right;
            }
        }
        reverse(ans.begin() + right + 1, ans.end());
        return ans;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        n = len(nums)
        ans = [pivot] * n
        left, right = 0, n - 1

        for i in range(n):
            if nums[i] < pivot:
                ans[left] = nums[i]
                left += 1
            elif nums[i] > pivot:
                ans[right] = nums[i]
                right -= 1
        
        x, y = right + 1, n - 1
        while x < y:
            ans[x], ans[y] = ans[y], ans[x]
            x += 1
            y -= 1
        
        return ans

复杂度分析

  • 时间复杂度：O(n)，其中 n 是数组 nums 的长度。

  • 空间复杂度：O(1)。这里不考虑答案数组需要使用的空间。

 Comments
On this page
2161-根据给定数字划分数组