LeetCode Wiggle Sort II
Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....
Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].
Note:
You may assume all input has valid answer.
Follow Up:
Can you do it in O(n) time and/or in-place with O(1) extra space?
给定一个数组，对其进行wiggle排序，如果下标从0开始，则奇数下标的数都要大于其相邻两个数，即nums[0] < nums[1] > nums[2] < nums[3]…. 普通解法是这样的，先给数组排序，然后设置首尾指针，分别取较小的数放到偶数位，较大的数放到奇数位。比如第一个样例排序之后是[1,1,1,4,5,6]，i指向1，j指向6，开辟一个新数组，依次把nums[i++]和nums[j–]放到新数组中，形成[1,6,1,5,1,4]，满足要求。 但是有一种情况会出问题，比如[4,5,5,6]，按上面的方法，得到的数组是[4,6,5,5]，最后的5,5不满足要求，究其原因，是因为随着i和j的推进，他们指向的数的差值越来越小，导致最后可能出现相等的情况。遇到这种情况，我们可以设置i从mid开始取，j从n-1开始取，这样i和j指向的数的差值始终是很大的，这样得到的结果就是[5,6,4,5] 因为题目说每个样例都有解，而wiggle sort的结果是先小后大，所以小数的个数总是大于等于大数的个数，比如1,2,1小数的个数大于大数的个数，1,2,1,2小数的个数等于大数的个数。所以我们i从mid开始时，如果数组有偶数个数，则中位数有两个，我们的mid应该是前一个中位数，这样能保证小数个数等于大数个数；如果数组有奇数个数，则中位数只有一个，我们的mid就从这个中位数开始，这样小数个数比大数个数多1。 所以第一个版本我们可以 [cpp] class Solution { private: //自己实现的快排程序 void my_quick_sort(vector<int>& nums, int s, int t) { int i = s, j = t, pivot = s; if (i >= j)return; while (i <= j) { while (i <= j&&nums[i] <= nums[pivot])++i; if (i > j)break; while (i <= j&&nums[j] >= nums[pivot])–j; if (i > j)break; swap(nums[i++], nums[j–]); } swap(nums[pivot], nums[j]); my_quick_sort(nums, s, j – 1); my_quick_sort(nums, j + 1, t); } public: void wiggleSort(vector<int>& nums) { int n = nums.size(); my_quick_sort(nums, 0, n – 1); int i = (n & 1) == 0 ? n / 2 – 1 : n / 2, j = n – 1; vector<int> ans(n, 0); for (int k = 0; k < n; ++k) { ans[k] = (k & 1) == 0 ? nums[i–] : nums[j–]; } nums = ans; } }; [/cpp] 手工写了快排程序，并手工根据n的奇偶性对i赋不同的值。本代码提交AC，用时569MS。自己写的快排是有多慢呀。 我们也可以这样 [cpp] class Solution { public: void wiggleSort(vector<int>& nums) { sort(nums.begin(), nums.end()); int n = nums.size(), i = (n + 1) / 2, j = n; vector<int> ans(n, 0); for (int k = 0; k < n; ++k) { ans[k] = (k & 1) == 0 ? nums[–i] : nums[–j]; } nums = ans; } }; [/cpp] 使用库中的sort，并且(n+1)/2相当于得到了偶数长的较大的中位数，或者奇数长中位数的下一个数，为了校准，进行了–i处理。本代码提交AC，用时86MS。 讨论区还有O(n)时间O(1)空间的解法，下回再战。]]>