我目前正在解决LeetCode问题2161。根据给定的主元对数组进行分区:
您将获得一个0索引整数数组
和一个整数nums。重新排列pivot以满足以下条件：nums
小于
的每个元素都出现在大于pivot的每个元素之前。pivot等于
的每个元素都出现在小于和大于pivot的元素之间。pivot小于
pivot的元素和大于的元素的pivot相对顺序保持不变。
- 更正式地说，考虑每个
、pi，其中pj是pi元素的新位置，ith是pj元素的新位置。对于小于jth的元素，如果pivot和i < j和nums[i] < pivot，则nums[j] < pivot。同样，对于大于pi < pj的元素，如果pivot和i < j和nums[i] > pivot，则nums[j] > pivot。pi < pj重新排列后
返回nums。示例：
输入：
,nums = [9,12,5,10,14,3,10]pivot = 10
输出：[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)与 Matt Timmermans 的答案略有不同，您可以首先从输入数组中删除主值（将其他值打包到其左侧），然后应用 O(𝑛log𝑛) 分而治之算法重复合并已由主元分区的两个子数组，旋转中心两个分区（四个分区中的）。然后最后将删除的主元值插入到剩余的两个分区之间。 为了避免消耗 O(log𝑛) 堆栈空间，请以自下而上的方式执行分而治之算法（无递归）。
这是一个实现：
class Solution {
void sliceRotateLeft(int[] arr, int start, int end, int shift) {
// Rotation in O(𝑛), where 𝑛 is the size of the array slice
int size = end - start;
if (size <= 1) return;
shift %= size;
if (shift == 0) return;
for (int count = 0, first = 0; count < size; first++, count++) {
int j = first;
int value = arr[start + j];
for (int i = j + shift; i != first; j = i, i = (i + shift) % size) {
arr[start + j] = arr[start + i];
count++;
}
arr[start + j] = value;
}
}
int sliceFindPivotIndex(int[] arr, int start, int end, int pivot) {
// Linear search. NB: binary search would be possible,
// but does not improve overall complexity.
while (start < end && arr[start] < pivot) start++;
return start;
}
public int[] pivotArray(int[] nums, int pivot) {
// Phase 1: pack all non-pivot values to the left
int len = 0; // Number of non-pivot values
for (int i = 0; i < nums.length; i++) {
if (nums[i] != pivot) nums[len++] = nums[i];
}
// Phase 2: partition non-pivot values into less-than, greater-than
// Use bottom up divide-and-conquer
for (int size = 1; size < len; size *= 2) {
// Merge two correctly partitioned chunks into one combined chunk
for (int start = 0; start + size < len; start += size * 2) {
// Get the offsets of the partitioned subarrays
int mid = start + size;
int end = Math.min(mid + size, len);
int left = sliceFindPivotIndex(nums, start, mid, pivot);
int right = sliceFindPivotIndex(nums, mid, end, pivot);
sliceRotateLeft(nums, left, right, mid - left);
}
}
// Phase 3: inject the pivot values
int pivotFrequency = nums.length - len;
int i;
for (i = len - 1; i >= 0 && nums[i] > pivot; i--) {
nums[i + pivotFrequency] = nums[i];
}
for (i++; pivotFrequency > 0; i++, pivotFrequency--) {
nums[i] = pivot;
}
return nums;
}
}
首先进行递归调用来划分下半部分和上半部分，这样你的数组就会像
lphLPH那样排序。然后从
pLlLphPHhPlLpPhH