my java solution,it is fast and easy to understand


  • 2
    L

    hi! every body! this my solution. I am trying to explain how i solve it;
    when we get an array such as [1, 5, 1, 1, 6, 4] ,we know one possible answer is [1, 4, 1, 5, 1, 6]. and it matches nums[0] < nums[1] > nums[2] < nums[3]...then we split them to pairs ,we find that every pair it satisfy nums[i] < nums[i+1] .and we can sort the array and we divide it to small part[1,1,1] and big part[6,5,4]. then we reorder the array just like that [1,6,1,5,1,4]. Ok,now it has been satisfy the nums[i] < nums[i+1]
    and also satisfy nums[i] < nums[i+1] > nums[i+2] (i start from 0) why? because nums[i+1] it is belong to the big part[6,5,4] and nums[i] , nums[i+1] are belong to the
    small part[1,1,1]. that is how i solve it!
    there is one point should be noticed: the small part and big part order should be desc not asc. why? because the biggest in the small part may be equal to the smallest in the big part.

     public static  void wiggleSort(int[] nums) {
       
       //[1,1,1,4,5,6]
        Arrays.sort(nums);
        
        int len = nums.length;
        //the big num index need to move 
        //when the len is odd the index should be add 1;
        //make sure that a1 >= a2
        int index = (int)Math.round(new Double(len) / 2);
        
        
        int[] a1 = new int[index];
        //[1,1,1]
        int k = 0;
        for(int i = index - 1; i >= 0; i--){
            a1[k++] = nums[i];
        }
        int[] a2 = new int[len - index];
        //[6,5,4]
        k = 0;
        for(int i = len - 1; i >= index; i--){
            a2[k++] = nums[i];
        }
        
        //at last fill the nums array
        k = 0;
        for(int i = 0; i < index && k < len; i++, k+=2){
            nums[k] = a1[i];
            if(k < len - 1){
              nums[k+1] = a2[i];  
            }
        }
        
        
        
    }

  • 0
    C

    hey,man,my idea is similar with yours~
    public static void Solution(int[] nums){
    Arrays.sort(nums);
    int mid = (nums.length+1)/2 - 1;
    int temp[] = new int[nums.length];
    int count = 0;
    int high = nums.length-1;
    while(count < nums.length){
    if(count%2 == 0){
    temp[count] = nums[mid--];
    }else{
    temp[count] = nums[high--];
    }
    count++;
    }
    for(int i=0;i<nums.length;i++){
    nums[i] = temp[i];
    }
    }


  • 0

    This is one straight forward solution. But company like google will not satisfy this solution. The follow up will ask you for in place solution with O(n) time complexity.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.