跳转至

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

题目描述

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

  • 所有小于 pivot 的元素都出现在所有大于 pivot 的元素 之前 。
  • 所有等于 pivot 的元素都出现在小于和大于 pivot 的元素 中间 。
  • 小于 pivot 的元素之间和大于 pivot 的元素之间的 相对顺序 不发生改变。
    • 更正式的，考虑每一对 pi，pj ，pi 是初始时位置 i 元素的新位置，pj 是初始时位置 j 元素的新位置。如果 i < 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 中的一个元素。

解法

方法一：模拟

我们可以遍历数组 \(\textit{nums}\)，按顺序找出所有小于 \(\textit{pivot}\) 的元素，所有等于 \(\textit{pivot}\) 的元素，以及所有大于 \(\textit{pivot}\) 的元素，然后将它们按照题目要求的顺序拼接起来。

时间复杂度 \(O(n)\)，其中 \(n\) 为数组 \(\textit{nums}\) 的长度。忽略答案数组的空间消耗，空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
        a, b, c = [], [], []
        for x in nums:
            if x < pivot:
                a.append(x)
            elif x == pivot:
                b.append(x)
            else:
                c.append(x)
        return a + b + c

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] pivotArray(int[] nums, int pivot) {
        int n = nums.length;
        int[] ans = new int[n];
        int k = 0;
        for (int x : nums) {
            if (x < pivot) {
                ans[k++] = x;
            }
        }
        for (int x : nums) {
            if (x == pivot) {
                ans[k++] = x;
            }
        }
        for (int x : nums) {
            if (x > pivot) {
                ans[k++] = x;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> pivotArray(vector<int>& nums, int pivot) {
        vector<int> ans;
        for (int& x : nums) {
            if (x < pivot) {
                ans.push_back(x);
            }
        }
        for (int& x : nums) {
            if (x == pivot) {
                ans.push_back(x);
            }
        }
        for (int& x : nums) {
            if (x > pivot) {
                ans.push_back(x);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func pivotArray(nums []int, pivot int) []int {
    var ans []int
    for _, x := range nums {
        if x < pivot {
            ans = append(ans, x)
        }
    }
    for _, x := range nums {
        if x == pivot {
            ans = append(ans, x)
        }
    }
    for _, x := range nums {
        if x > pivot {
            ans = append(ans, x)
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function pivotArray(nums: number[], pivot: number): number[] {
    const ans: number[] = [];
    for (const x of nums) {
        if (x < pivot) {
            ans.push(x);
        }
    }
        if (x === pivot) {
            ans.push(x);
        }
    }
    for (const x of nums) {
        if (x > pivot) {
            ans.push(x);
        }
    }
    return ans;
}

方法二：双指针

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function pivotArray(nums: number[], pivot: number): number[] {
    const n = nums.length;
    const res = Array(n).fill(pivot);

    for (let i = 0, l = 0, j = n - 1, r = n - 1; i < n; i++, j--) {
        if (nums[i] < pivot) res[l++] = nums[i];
        if (nums[j] > pivot) res[r--] = nums[j];
    }

    return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
function pivotArray(nums, pivot) {
    const n = nums.length;
    const res = Array(n).fill(pivot);

    for (let i = 0, l = 0, j = n - 1, r = n - 1; i < n; i++, j--) {
        if (nums[i] < pivot) res[l++] = nums[i];
        if (nums[j] > pivot) res[r--] = nums[j];
    }

    return res;
}

评论