Given an integer array nums, reorder it such that nums[0] &lt; nums[1] &gt; nums[2] &lt; nums[3]....

You may assume the input array always has a valid answer.

&nbsp;
Example 1:

Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also accepted.


Example 2:

Input: nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 5 * 104
	0 &lt;= nums[i] &lt;= 5000
	It is guaranteed that there will be an answer for the given input nums.


&nbsp;
Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?
class Heap:
	def __init__(self):
		self.q = []
	def push(self,data):
		i = len(self.q)
		self.q.append(data)
		while i>0:
			if self.q[i] > self.q[(i-1)//2]:
				self.q[i], self.q[(i-1)//2] = self.q[(i-1)//2], self.q[i]
				i = (i-1)//2
			else: return 
	def pop(self):
		if len(self.q)==0:return
		self.q[0] = self.q[-1]
		self.q.pop()
		def heapify(i):
			ind = i
			l = 2*i+1
			r = 2*i+2
			if r<len(self.q) and self.q[ind] < self.q[r]: ind = r
			if l<len(self.q) and self.q[ind] < self.q[l]: ind = l            
			if ind != i:
				self.q[i], self.q[ind] = self.q[ind], self.q[i]
				heapify(ind)
		heapify(0)
	def top(self):  
		return self.q[0] 


class Solution:
	def wiggleSort(self, nums: List[int]) -> None:
		n = len(nums)
		h = Heap()
		for i in nums: h.push(i)
		for i in range(1,n,2):
			nums[i] = h.top()
			h.pop()
		for i in range(0,n,2):
			nums[i] = h.top()
			h.pop()
class Solution {
    public void wiggleSort(int[] nums) {
        int a[]=nums.clone();
        Arrays.sort(a);
        int left=(nums.length-1)/2;
        int right=nums.length-1;
        for(int i=0;i<nums.length;i++){
            if(i%2==0){
                nums[i]=a[left];
                left--;
            }
            else{
                nums[i]=a[right];
                right--;
            }
        }
    }
}
class Solution {
public:
    void wiggleSort(vector<int>& nums) {

        priority_queue<int> pq;
        for(auto &i : nums)
            pq.push(i);

        for(int i = 1; i < nums.size(); i += 2)
            nums[i] = pq.top(), pq.pop();

        for(int i = 0; i < nums.size(); i += 2)
            nums[i] = pq.top(), pq.pop();
    }
};
var wiggleSort = function(nums) {
    nums.sort((a,b) => a - b);

    let temp = [...nums];

    let low = Math.floor((nums.length-1)/2), high = nums.length-1;

    for(let i=0; i < nums.length; i++){
        if(i % 2 === 0){
            nums[i] = temp[low];
            low--;
        }else{
            nums[i] = temp[high];
            high--;
        }
    }

    return nums;
};
Wiggle Sort II