324. Wiggle Sort II

时间:2023-03-08 23:57:13
324. Wiggle Sort II

这个题真是做得我想打人了。我生起气来连自己都打。

324. Wiggle Sort II

一开始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;
}
}
}