AC In-place O(n) Java Solution


  • 0
    U
    public class Solution {// odd index ele>= surrounding even elements.
    public void wiggleSort(int[] nums) {
        if(nums.length==1)
            return;
        int index=0;
        int k=0;
        while(index<nums.length){
            index=2*k+1;// do not write 2k+1; for each odd index search its +1 -1 region, find the max element then swap. eg for index 1, serach index0,1,2. 
            int upbound=2*k+2;
            int max=2*k;
            if(2*k+2>nums.length-1){
                for(int i=2*k;i<nums.length;i++){
                    if(nums[i]>=nums[max])
                        max=i;
                }
                swap(nums,2*k+1,max);
            }
            else{
                for(int i=2*k;i<=upbound;i++){
                    if(nums[i]>=nums[max])
                        max=i;
                }
                swap(nums,2*k+1,max);
            }
            k++;
            if(2*k+1>=nums.length)
                break;
            
        } 
    }
    private void swap(int[] nums, int index1, int index2){
        int temp= nums[index1];
        nums[index1]=nums[index2];
        nums[index2]=temp;
    }
    

    }


  • 0
    U

    However,I am not sure about the time complexity. can someone tell me, thanks in advance.


Log in to reply
 

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