这个题真是做得我想打人了。我生起气来连自己都打。
一开始quick select没啥可说的。但是in place把老命拼了都没想出来。。
看网上的答案是3 partition，MAP式子一看就由衷地反胃。。
老子不管了，就O(n)。。
public class Solution
{
public void wiggleSort(int[] nums)
{
if(nums.length <= 1 ) return;
if(nums.length == 2)
{
if(nums[0] > nums[1]) swap(0,1,nums);
return;
}
//start of larger half
int m = (nums.length+1)/2;
int mVal = nums[quickSelect(nums,m,0,nums.length-1)];
int[] res = new int[nums.length];
int a = 0, b = nums.length-1;
for(int i = 0; i < res.length;i++)
{
if(nums[i] < mVal)
{
res[a] = nums[i];
a++;
}
else if(nums[i] > mVal)
{
res[b] = nums[i];
b--;
}
}
while(a < m) res[a++] = mVal;
while(b >= m) res[b--] = mVal;
//System.out.println(a + " " + b + " " + m + " " + mVal);
b = nums.length-1;
a-=1;
for(int i = 0; i < nums.length;i++)
{
if(i%2 == 0)
{
nums[i] = res[a];
a--;
}
else
{
nums[i] = res[b];
b--;
}
}
return;
}
public int quickSelect(int[] nums, int m, int L, int R)
{
int pIndex = awesomePick(L,R,nums);
int pVal = nums[pIndex];
swap(R,pIndex,nums);
int tempIndex = L;
for(int i = L; i < R;i++)
{
if(nums[i] <= pVal) swap(i,tempIndex++,nums);
}
swap(tempIndex,R,nums);
if(tempIndex == m) return tempIndex;
else if(tempIndex < m) return quickSelect(nums,m,tempIndex+1,R);
else return quickSelect(nums,m,L,tempIndex-1);
}
public void swap(int a, int b, int[] nums)
{
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
public int awesomePick(int L, int R, int[] nums)
{
int a = nums[L];
int b = nums[R];
int M = L+(R-L)/2;
int c = nums[M];
if( a > b )
{
if( b > c ) return R;
else if(a > c) return M;
else return L;
}
//b > a
else
{
if(a > c) return L;
else if(b > c) return M;
else return R;
}
}
}