Easily-understood Java solution (O(n) time and O(1) space)


  • 0
    H
    import java.util.Random;      
    public class Solution {
    int m = 0;
    public void wiggleSort(int[] nums) {
        if (nums.length < 2) return;
        int lt = 0, gt = nums.length-1, i = 0;
        m = (gt - 1)/2; //used for virtual index mapping, the number of items that are larger than mid should <= the number of items smaller than mid.
        int mid = quickSelect(nums, gt/2);
    	while (i <= gt) { //put the larger items in the left to handle the problem of duplicate items with the same value of mid, such as [4,5,5,6]
    		if (nums[idx(i)] > mid) swap(nums, idx(i++), idx(lt++));
    		else if (nums[idx(i)] < mid) swap(nums, idx(i), idx(gt--));
    		else i++;
    	}
    }
    private void swap(int[] nums, int x, int y) {
    	int temp = nums[x];
    	nums[x] = nums[y];
    	nums[y] = temp;
    }
    private int idx(int i) { //idea from https://leetcode.com/discuss/77133/o-n-o-1-after-median-virtual-indexing
    	if (i <= m) return 2*i+1;
    	else return 2*(i-m-1);
    }
    private int quickSelect(int[] a, int k) {
    	randomShuffle(a);
    	int lo = 0, hi = a.length-1;
    	while (lo < hi) {
    		int i = partition(a, lo, hi);
    		if (i > k) hi = i - 1;
    		else if (i < k) lo = i + 1;
    		else return a[i];
    	}
    	return a[lo];
    }
    private int partition(int[] a, int lo, int hi) {
    	int i = lo, j = hi + 1;
    	int pivot = a[lo];
    	while(true) {
    		while(a[++i] < pivot)
    			if (i == hi) break;
    		while(a[--j] > pivot)
    			if (j == lo) break;
    		if (i >= j) break;
    		swap(a, i, j);
    	}
    	swap(a, lo, j);
    	return j;
    }
    private void randomShuffle(int[] nums) {
        Random rm = new Random();
        for(int i = 0; i < nums.length-1; i++) {
            int j = i + rm.nextInt(nums.length-i);
            swap(nums, i, j);
        }
    }
    }

Log in to reply
 

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