package com.fishercoder.solutions;

import java.util.Collections;
import java.util.PriorityQueue;

/**
 * 324. Wiggle Sort II
 *
 * Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

 Example:
 (1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
 (2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

 Note:
 You may assume all input has valid answer.

 Follow Up:
 Can you do it in O(n) time and/or in-place with O(1) extra space?
 */
public class _324 {

    /**Credit: https://discuss.leetcode.com/topic/41464/step-by-step-explanation-of-index-mapping-in-java
     * TODO: completely understand it.*/
    public void wiggleSort(int[] nums) {
        int median = findKthLargest(nums, (nums.length + 1) / 2);
        int n = nums.length;

        int left = 0;
        int i = 0;
        int right = n - 1;

        while (i <= right) {

            if (nums[newIndex(i, n)] > median) {
                swap(nums, newIndex(left++, n), newIndex(i++, n));
            } else if (nums[newIndex(i, n)] < median) {
                swap(nums, newIndex(right--, n), newIndex(i, n));
            } else {
                i++;
            }
        }
    }

    private int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        for (int i : nums) {
            maxHeap.offer(i);
        }
        while (k-- > 1) {
            maxHeap.poll();
        }
        return maxHeap.poll();
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    private int newIndex(int index, int n) {
        return (1 + 2 * index) % (n | 1);
    }

}

@@ -552,15 +552,56 @@
  %7B%0A%0A
+    public static class Solution1 %7B%0A    
     /**
+ 
 Cred
@@ -698,50 +698,16 @@
 java
+ */
 %0A    
- * TODO: completely understand it.*/%0A
     
@@ -747,24 +747,28 @@
 ) %7B%0A        
+  
+  
 int median =
@@ -817,24 +817,28 @@
 2);%0A        
+    
 int n = nums
@@ -851,24 +851,28 @@
 h;%0A%0A        
+    
 int left = 0
@@ -869,24 +869,28 @@
 t left = 0;%0A
+    
         int 
@@ -900,24 +900,28 @@
  0;%0A        
+    
 int right = 
@@ -932,24 +932,28 @@
 1;%0A%0A        
+   
+ 
 while (i %3C= 
@@ -958,24 +958,28 @@
 = right) %7B%0A%0A
+    
             
@@ -1023,32 +1023,36 @@
                 
+ 
+   
 swap(nums, newIn
@@ -1082,24 +1082,28 @@
 x(i++, n));%0A
+    
             
@@ -1154,32 +1154,36 @@
                 
+    
 swap(nums, newIn
@@ -1224,24 +1224,28 @@
             
+   
+ 
 %7D else %7B%0A   
@@ -1241,16 +1241,20 @@
  else %7B%0A
+    
         
@@ -1270,34 +1270,42 @@
 ++;%0A            
-%7D%0A
+    %7D%0A    
         %7D%0A    %7D%0A
@@ -1298,27 +1298,35 @@
       %7D%0A    
-%7D%0A%0A
+    %7D%0A%0A    
     private 
@@ -1361,24 +1361,28 @@
 s, int k) %7B%0A
+    
         Prio
@@ -1467,16 +1467,20 @@
         
+  
+  
 for (int
@@ -1484,32 +1484,36 @@
 int i : nums) %7B%0A
+    
             maxH
@@ -1534,26 +1534,33 @@
         
-%7D%0A
+    %7D%0A   
         
 while (k
@@ -1547,24 +1547,25 @@
 %0A           
+ 
 while (k-- %3E
@@ -1574,32 +1574,36 @@
 ) %7B%0A            
+    
 maxHeap.poll();%0A
@@ -1602,34 +1602,42 @@
 poll();%0A        
+  
-%7D%0A
+  %7D%0A    
         return m
@@ -1651,27 +1651,35 @@
 poll();%0A    
+ 
-%7D%0A%0A
+   %7D%0A%0A    
     private 
@@ -1720,24 +1720,28 @@
 ) %7B%0A        
+    
 int tmp = nu
@@ -1751,24 +1751,28 @@
 i%5D;%0A        
+  
+  
 nums%5Bi%5D = nu
@@ -1782,24 +1782,28 @@
 j%5D;%0A        
+    
 nums%5Bj%5D = tm
@@ -1805,27 +1805,35 @@
  = tmp;%0A    
+ 
-%7D%0A%0A
+   %7D%0A%0A    
     private 
@@ -1869,24 +1869,28 @@
 ) %7B%0A        
+    
 return (1 + 
@@ -1915,13 +1915,22 @@
 1);%0A    
+    %7D%0A    
 %7D
-%0A
 %0A%7D%0A

refactor 324