Java Solution with Explanation & Thoughts


  • 3
    Y

    The basic idea is to make sure that every odd position is greater than (or equal to) its two adjacent even postions. For example, if the current odd position is i, then we need to make sure the nums[i-1] <= nums[i] and nums[i+1] <= nums[i]. If you do that for the entire array, then the result will satisfy Wiggle Sort's requirement. (It's kind of like a greedy solution IMO, where local optimum leads to global optimum).

    I also thought about the proof (please tell me if i'm wrong here). I was wondering if there could be a case where a group of 3 numbers couldn't be arranged to meet the requirement. Turns out this is not the case. Let's say we have 3 consecutive numbers in the mid of the array a, b, and c, where b is at an odd index and a, c are at even indices. There are only 4 possible cases:
    1. a <= b <= c --> swap(b, c)
    2. a <= b >= c --> done
    3. a >= b <= c --> swap(a, b), then it could be either case 1 or 2
    4. a >= b >= c --> swap(a, b)
    Whatever the case it is, we will always be able to satisfy the requirement nums[i-1] <= nums[i] and nums[i] >= nums[i+1]. In addition, whether we swap (a, b) or not, it will still maintain the correct order for the previous group (e.g. if we have d, a, b, c where d >= a. If a >= b then we swap(a, b), but still d >= b). Thus, if we do this operation to each [even, odd, even] index group of the array, then we should have the final solution.

    My code can be more concise, but I want it to be crystal clear so I wrote it in the more verbose way.

    public class Solution {
        public void wiggleSort(int[] nums) {
            for (int i = 1; i < nums.length; i++) {
                if (i % 2 == 0 && nums[i-1] < nums[i]) {  // at even index, check if it's greater than previous number
                    swap(nums, i-1, i);
                }
                if (i % 2 != 0 && nums[i-1] > nums[i]) {  // at odd index, check if it's smaller than previous number
                    swap(nums, i-1, i);
                }
            }
        }
        
        private void swap(int[] arr, int i, int j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    

  • -2
    V

    what if it's consecutive same numbers, let's assume:
    [1,1,1,1,1,2,2,2,2,2] and your solution bugged.


  • 0
    Y

    @vincent.zou Notice this is wiggle sort 1 not 2: nums[0] <= nums[1] >= nums[2] <= nums[3]


  • -2
    V

    just run your code, and your code simply output:
    [1,1,1,1,1,2,2,2,2,2]
    when input
    [1,1,1,1,1,2,2,2,2,2].

    because nums[i-1] == nums[i], and you simply do nothing in your code right?


  • 0
    Y

    @vincent.zou The input you given is already an acceptable result.


  • 0
    C

    @yuhao5 Nice solution!


Log in to reply
 

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