根据给定数字划分数组

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

P-题解

总体来说时空都是比较占优的空间损耗也不大

双指针left从0开始递增以及right从数组后置位开始递减，分别用作于比较大于pivot以及小于pivot的，优点在于能够按照原本的次序在新的数组里面安排位置。
其实等于pivot可以不做比较，可以在新数组的所有元素填满pivot值，然后通过与原数组比较前后开始占位变值。

其实这里的时间复杂度应该是O（N）的。

public int[] pivotArray(int[] nums, int pivot) {
    int left =0;
    int length =nums.length;
    int right =length-1;
    int newNum[] = new int [length];
    Arrays.fill(newNum,pivot);
    for(int min=0,max=length-1;left<length&&right>=0;left++,right--){
        if(nums[left]<pivot){
            newNum[min++]=nums[left];
        }
        if(nums[right]>pivot){
            newNum[max--]=nums[right];
        }
    }
    return newNum;
}

O-题解

简单的三次遍历

时间较快，空间损耗相对大

public int[] pivotArray(int[] nums, int pivot) {
    int n = nums.length, k = 0;
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) if (nums[i] < pivot) ans[k++] = nums[i];
    for (int i = 0; i < n; i++) if (nums[i] == pivot) ans[k++] = nums[i];
    for (int i = 0; i < n; i++) if (nums[i] > pivot) ans[k++] = nums[i];
    return ans;
}

划分以及拼接

运行时间可以说是题解里最长的了，而且空间也不是最优秀的。可能是因为增强for循环的或者计算长度的原因，比上面多一次循环的方法时间还要久。

三个数据类型为Integer的ArrayList对象，分别储存三个不同的情况的数值
计算所有List的长度，建立新的数组，增强循环来依次输入顺序数值

public int[] pivotArray(int[] nums, int pivot) 
{
    List<Integer> a = new ArrayList<>();
    List<Integer> b = new ArrayList<>();
    List<Integer> c = new ArrayList<>();

    for (int x: nums)
    {
        if (x < pivot)
        {
            a.add(x);
        }
        else if (x == pivot)
        {
            b.add(x);
        }
        else
        {
            c.add(x);
        }
    }

    int n = a.size() + b.size() + c.size();
    int [] res = new int [n];
    int i = 0;
    for (int x : a)
    {
        res[i ++] = x;
    }
    for (int x : b)
    {
        res[i ++] = x;
    }
    for (int x : c)
    {
        res[i ++] = x;
    }
    return res;
}