我目前正在解决根据给定主元进行数组分区的 Leetcode 问题。
<强> Problem :
You are given a
0
-indexed integer arraynums
and an integerpivot
. Rearrangenums
such that the following conditions are satisfied:Every element less than
pivot
appears before every element greater thanpivot
.Every element equal to
pivot
appears in between the elements less than and greater thanpivot
.The relative order of the elements less than
pivot
and the elements greater thanpivot
is maintained.More formally, consider every
pi
,pj
wherepi
is the new position of thei
th element andpj
is the new position of thejth
element. For elements less than pivot, ifi < j
andnums[i] < pivot
andnums[j] < pivot
, thenpi < pj
. Similarly for elements greater thanpivot
, ifi < j
andnums[i] > pivot
andnums[j] > pivot
, thenpi < 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)
不过空间复杂度是可能的。
最佳答案
您可以在 O(n log n) 时间内递归地解决这个问题。
首先进行递归调用来划分下半部分和上半部分,以便您的数组像 lphLPH
那样排序。然后从p
旋转到L
得到lLphPH
。然后旋转hP
得到lLpPhH
关于java - 力扣 : Partition array according to a pivot,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/76942786/