LeetCode Wiggle Sort II

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。

所以第一个版本我们可以

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;
	}
};

手工写了快排程序,并手工根据n的奇偶性对i赋不同的值。本代码提交AC,用时569MS。自己写的快排是有多慢呀。

我们也可以这样

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;
	}
};

使用库中的sort,并且(n+1)/2相当于得到了偶数长的较大的中位数,或者奇数长中位数的下一个数,为了校准,进行了--i处理。本代码提交AC,用时86MS。

讨论区还有O(n)时间O(1)空间的解法,下回再战。

Leave a Reply

Your email address will not be published. Required fields are marked *