c# n(log(n)) easy understand solution without using virtual index and three way partition.


  • 0
    N

    there is no build-in nth selection method in c#. so i just sort it. it takes O(nlogn) runtime and o(n) space, but should be much easy to understand.

    public class Solution {
        public void WiggleSort(int[] nums) {
            if(nums.Length<=1) return ;
            Array.Sort(nums);
            var copy = nums.Clone() as int[];
            var mid = nums.Length%2 ==0? (nums.Length/2-1): (nums.Length/2); // right base mid index
            for(var i=0;i<nums.Length;i++){
                nums[i] = i%2==0? copy[mid-i/2]: copy[nums.Length-1 - i/2]; // refer to https://discuss.leetcode.com/topic/41464/step-by-step-explanation-of-index-mapping-in-java
            }
        }
    }
    

Log in to reply
 

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