力扣leetcode 最简单的中等题 2161. 根据给定数字划分数组

力扣leetcode

题目链接与描述

https://leetcode.cn/problems/partition-array-according-to-given-pivot/

给你一个下标从 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 中的一个元素。

关键词：

方法一：暴力求解

运行截图

代码

public  int[] pivotArray(int[] nums, int pivot) {
		// 1.暴力求解：
		// 分析题目：分三组，小 、等 、 大
		// 	另外分别要维持自身原顺序

		// 不知道各自多长，所以不用数组，创建三个列表：小、等、大
		List<Integer> letter = new ArrayList<>();
		List<Integer> eq = new ArrayList<>();
		List<Integer> grater = new ArrayList<>();
		// 遍历入参，小的丢小列表。。。
		for (int num : nums) {
			if (num < pivot) {
				letter.add(num);
			} else if (num == pivot) {
				eq.add(num);
			} else {
				grater.add(num);
			}
		}
		// 完事把等于、大于 往小于上面接
		letter.addAll(eq);
		letter.addAll(grater);
		// 最后转成int 数组，这里用intStream 省得麻烦
		return letter.stream().mapToInt(s -> s).toArray();
	}


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

方法二：快慢指针+反转

运行截图

代码

可以看到暴力求解法，时间复杂度是n，空间复杂度是3n
那我们可以分析一下，怎么把空间缩小
因为返回数组是和原数组相同长度，而且比较的是大和小，很容易联想到左、右指针，中间放相等即可

	public static int[] pivotArray2(int[] nums, int pivot) {
		 
		int l = 0, r = nums.length - 1;
		int[] ret = new int[nums.length];
		for (int num : nums) {
			if (num > pivot) {
				// 注意这里是反方向
				ret[r--] = num;
			} else if (num < pivot) {
				ret[l++] = num;
			}
		}

		// 填补中间相等
		for (int i = l; i <= r; i++) {
			ret[i] = pivot;
		}

		// 反转 大于
		int end = nums.length - 1;
		r++;
		while (r < end) {
			int tmp = ret[r];
			ret[r++] = ret[end];
			ret[end--] = tmp;
		}
		return ret;
	}

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

结尾

欢迎评论区交流，每日打卡，冲冲冲！！！