2161.根据给定数字划分数组
1.题目描述
给你一个下标从 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] <= 106pivot等于nums中的一个元素。
2.解题思路
思路1 先划分再合并
这个思路比较直观，因为我们要把这个数组分为<,=,> pivot的三个部分，然后每一个部分都要保证它们中的元素是按照数组中原有的顺序排列的，所以我们就通过一次遍历，分别把符合上述三个数组的元素add进各自的list，遍历结束后，再依次把= ,> pivot的元素全部添加到< pivot的list中，就得到了题目中所求。
思路2 双指针
这个思路是在一开始就初始化一个值全部等于pivot的数组res,然后让left指针指向第一个元素，right指针指向最后一个元素，在遍历nums的过程中，遇到<pivot的元素，就把left指向的元素替换小于它的元素，然后left+=1，遇到>pivot的元素就把right指向的元素替换为>它的元素，然后right-=1，遇到等于pivot的元素就无需做任何处理，因为我们的res数组就是用pivot初始化的。这样遍历nums结束后，从right+1位置到n-1位置就是所有>pivot的元素，但是它们的顺序是倒序插入的，因此还要做一步reverse的操作，再次使用双指针，依次交换left,right指向元素即可。
3.代码实现
思路1
class Solution {public int[] pivotArray(int[] nums, int pivot) {List<Integer> lt = new ArrayList<>();List<Integer> eq = new ArrayList<>();List<Integer> gt = new ArrayList<>();for (int num : nums) {if (num < pivot) {lt.add(num);} else if (num == pivot) {eq.add(num);} else {gt.add(num);}}lt.addAll(eq);lt.addAll(gt);return lt.stream().mapToInt(Integer::intValue).toArray();}
}思路2
class Solution {public int[] pivotArray(int[] nums, int pivot) { int n = nums.length;int[] res = new int[n];Arrays.fill(res,pivot);int left = 0, right = n - 1;//左指针找比pivot小的元素,右指针找比pivot大的元素for (int i = 0; i < n; i++) {if (nums[i] < pivot) {res[left++] = nums[i];} else if (nums[i] > pivot) {res[right--] = nums[i];}}//右指针对应区域逆序left = right + 1;right = n - 1;while (left < right) {int temp = res[left];res[left] = res[right];res[right] = temp;left += 1;right -= 1;}return res;}
}