//问题：摆动排序，a[0] < a[1] > a[2] < a[3]...
//？？没看懂，以后再看
//方法二：利用快排中一步（nth_element函数）将序列分成两段，以中值为枢轴，从各段段首（或段尾）开始选数
//思路解析：假设排序后为a1 a2...an mid b1 b2...bn,则组织为a1 b1 a2 b2...
//此法时间复杂度为O（n）,如果没有O(1)的空间复杂度，比较简单，正是这个限制增加了复杂度
class Solution {
public:
void wiggleSort(vector<int>& nums) {
int m = nums.size();
auto mptr = nums.begin() + (m-1)/2;
nth_element(nums.begin(), mptr, nums.end());
int median = *mptr;
int i = 1; // position for the larger values: start with first odd index
int j = ((m - 1) & 1) ? m - 2 : m - 1; // position for the smaller values: start with last even index
for (int l = 0; l < m; ++l) {
if (nums[l] > median) { // fill the large element
if (l <= i && (l & 1)) continue; // skip the elements which are already checked: 1, 3, 5, ..., i
swap(nums[l--], nums[i]);
i += 2;
} else if (nums[l] < median) { // fill the smaller element
if (l >= j && (l & 1) == 0) continue; // skip the elements whcih are checked: j, j + 2, ..., lastEvenIndex
swap(nums[l--], nums[j]);
j -= 2;
}
}
}
};
//方法一：排序后，分成两段，从各段末尾依次取数（可以避免相等数弄在一起）
//不过此法的时间复杂度为O(nlogn)，空间复杂度为O(n),不满足题意
//思路解析：假设排序后为a1 a2...an b1 b2...bn,则组织为an bn an-1 bn-1...
class Solution
{
public:
void wiggleSort(vector<int>& a)
{
int n = a.size();
sort(a.begin(),a.end());
if(n<=2) return; //小于两个元素时，直接退出
vector<int> temp = a;
int i = 0, j=(n-1)/2, k=n-1; //i用来遍历a, j用来遍历temp第一段（从末尾开始），k用来遍历第二段。
for(i = 0; i < n; i++)
{
a[i] = (i&1)? temp[k--]:temp[j--];//如果i为奇数,取第二段的数（较大），如果为偶数，取第一段的数（较小）
//注：当n为奇数时，两段长度不等，第一段比第二段多1，但是上述等式可以保证最后一个数a[n-1]选择temp[0]
}
}
};
/*
//摆动排序，a[0] < a[1] > a[2] < a[3]...
//要得到O(n)时间复杂度，O(1)空间复杂度，可以借鉴wiggle sort I（a[0] <= a[1] >= a[2] <= a[3]...）中的思路
//i为奇数时，a[i]>a[i-1], 偶数时，a[i]<a[i-1], 根据这一规律，遍历整个序列，不符合则交换
//测试结果表明，对于序列中有多个连续相等数时，此方法不行，因为按照交换策略，相等的数会交换，但是交换后并不会满足
//i为奇数时，a[i]>a[i-1], 偶数时，a[i]<a[i-1]的规律，而是仍然相等。
class Solution
{
public:
void wiggleSort(vector<int>& a)
{
int n = a.size();
if(n <= 1) return; //元素个数少于1个时，退出
for(int i = 1; i < n; i++)
{
if((i%2 == 1 && a[i]<=a[i-1]) || (i%2 == 0 && a[i]>=a[i-1]))
{
swap(a[i], a[i-1]);//如果不符合摆动规律则交换
}
}
}
};
*/
