Three-way Partition

问题来源于the Dutch national flag problem，荷兰国旗问题？

把数组重新排序，比mid小的在前面，等于mid的在中间，比mid大的在最后，类似于快速排序中的partition

循环里，i <= j 保持不变，n是比mid大的数字在数组中的索引下界，j是当前考虑的数字的索引，i是比mid小的数字在数组中的索引上界，只有当遇到mid时j才会大于i

void partition(vector<int>& arr, int mid){int i = 0, j = 0, n = arr.size() - 1;while(j <= n){if(arr[j] < mid)swap(arr[i++], arr[j++]);else if(arr[j] > mid)swap(arr[j], arr[n--]);elsej = j + 1;} }

时间复杂度为O(n)

空间复杂度O(1)

 

LeetCode 326 Wiggle Sort II

Give an unsorted array nums, reorder it such that $nums[0] < nums[1] > nums[2] < nums[3]....$, assume all input has valid answer.

O(n) time O(1) extra space

void wiggleSort(vector<int>& nums) {int n = nums.size();// Find a median.auto midptr = nums.begin() + n / 2;nth_element(nums.begin(), midptr, nums.end());int mid = *midptr;// Index-rewiring.#define A(i) nums[(1+2*(i)) % (n|1)]// 3-way-partition-to-wiggly in O(n) time with O(1) space.int i = 0, j = 0, k = n - 1;while (j <= k) {if (A(j) > mid)swap(A(i++), A(j++));else if (A(j) < mid)swap(A(j), A(k--));elsej++;} }

Virtual indexing: map of subscript, from 0~mid to odd numbrs(1, 3, 5, 7...), and from mid + 1~n - 1 to even  numbers(0, 2, 4, 6...). So the big numbers which formerly in 0~mid will be placed in 1, 3, 5, 7..., and small numbers in 0, 2, 4, 6...

 

转载于:https://www.cnblogs.com/betaa/p/11465746.html

总结

以上是生活随笔为你收集整理的Three-way Partition的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。