Java, Sort, Reverse, then Swap


  • 0
    H
    1. Sort the array
    2. Reverse half of back parts.
    3. Insert the half of rear into interval of half of front

    If Arrays.sort() uses heap sort, it is in-place sort.
    If not, it is not in-place sort

    public class Solution {
        public void wiggleSort(int[] nums) {
            if(nums.length < 2 || nums == null) return;
            int mid = nums.length % 2 == 0 ? (nums.length/2) : (nums.length/2)+1;
            
            //sort
            Arrays.sort(nums);
            
            //reverse half of rear
            reverse(nums, mid, nums.length-1);
            
            //insert the half of rear into interval of half of front
            for(int i=1; i<=mid; i+=2){
                swap(nums, i, mid++);
                if(i+2>=nums.length) break;
            }
        }
        
        private void reverse(int[] nums, int start, int end){
            while(start<=end){
                swap(nums, start++, end--);
            }
        }
        
        private void swap(int[] nums, int start, int end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
        }
        
    }
    

Log in to reply
 

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