java - 力扣 : Partition array according to a pivot

Question

我目前正在解决根据给定主元进行数组分区的 Leetcode 问题。

<强> Problem :

You are given a 0-indexed integer array nums and an integer pivot. Rearrange nums such that the following conditions are satisfied:

Every element less than pivot appears before every element greater than pivot.

Every element equal to pivot appears in between the elements less than and greater than pivot.

The relative order of the elements less than pivot and the elements greater than pivot is maintained.

More formally, consider every pi, pj where pi is the new position of the ith element and pj is the new position of the jth element. For elements less than pivot, if i < j and nums[i] < pivot and nums[j] < pivot, then pi < pj. Similarly for elements greater than pivot, if i < j and nums[i] > pivot and nums[j] > pivot, then pi < pj.

Return nums after the rearrangement.

示例:

Input: nums = [9,12,5,10,14,3,10], pivot = 10

Output: [9,5,3,10,10,12,14]

我的解决方案:

解决方案 O(n)内存是微不足道的。我试图想出一个 O(1)内存解决方案并接近了类似于插入排序的方式:

public int[] pivotArray(int[] nums, int pivot) {
    for(int i = 0; i < nums.length; i++){
        if(nums[i] < pivot){
            for(int j = i; j > 0 && nums[j - 1] >= pivot; j--){
                int tmp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = tmp;
            }
        }
        if(nums[i] == pivot){
            for(int j = i; j > 0 && nums[j - 1] > pivot; j--){
                int tmp = nums[j];
                nums[j] = nums[j - 1];
                nums[j - 1] = tmp;
            }
        }
    }
    return nums;
}

问题是解决方案有 O(n^2)时间复杂度。有没有一种算法可以比O(n^2)更快地解决这个问题？我不确定是否O(n)时间和O(1)不过空间复杂度是可能的。

Answer 1

您可以在 O(n log n) 时间内递归地解决这个问题。

首先进行递归调用来划分下半部分和上半部分，以便您的数组像 lphLPH 那样排序。然后从p旋转到L得到lLphPH。然后旋转hP得到lLpPhH