Question:
http://www.lintcode.com/en/problem/wiggle-sort/
Given an unsorted array nums, reorder it in-place such that
nums[0] <= nums[1] >= nums[2] <= nums[3]....
Example
Given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
Answer:
http://www.lintcode.com/en/problem/wiggle-sort/
Given an unsorted array nums, reorder it in-place such that
nums[0] <= nums[1] >= nums[2] <= nums[3]....
Example
Given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].
Answer:
class Solution {
public:
/*
* @param nums: A list of integers
* @return: nothing
*/
inline int partion(vector<int> &nums, int left, int right) {
int pivot = nums[left];
int i = left - 1;
int j = right + 1;
while (1) {
do {
i = i + 1;
} while (nums[i] < pivot);
do {
j = j -1;
} while (nums[j] > pivot);
if (i >= j)
return j;
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
inline void qsort(vector<int> &nums, int left, int right) {
if (left >= right)
return;
int p = partion(nums, left, right);
qsort(nums, left, p);
qsort(nums, p+1, right);
}
void wiggleSort(vector<int> &nums) {
// write your code here
vector<int> sort = nums;
int len = nums.size();
qsort(sort, 0, len-1);
int l = 0;
int r = len - 1;
nums.clear();
while (l < r) {
nums.push_back(sort[l]);
nums.push_back(sort[r]);
l++;
r--;
}
if (l == r)
nums.push_back(sort[l]);
}
};
