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] <= 106
• pivot 等于 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;}
}