Java Solution O(n) Quick Select + O(1) Index Mapping 3 Way Partition


  • 0

    First, I use quick select to find value of median element in array in O(n);
    WHY O(n)?
    Think about quick sort with n * logn, now I just use n + n/2 + n/4 + n/8 + ... which is O(n) to perform quick select.
    Then the next move is index mapping:
    [0,1,2,3,4,5]-->[1,3,5,0,2,4]
    [0,1,2,3,4,5,6]-->[1,3,5,0,2,4,6]
    using function (i * 2 + 1) % (length | 1)
    Finally, use the same method in Sort Color (leetcode question) to do it in O(1).
    If you don't understand it, look at Sort Color first (3 way partition).

    Below is the code:

    public class Solution {
        private int length;
        public void wiggleSort(int[] nums) {
            // quick select O(n) + index mapping O(1)
            length = nums.length;
            int middle = quickselect(nums, 0, nums.length - 1, (nums.length - 1) / 2);
            int curr = 0;
            int left = 0;
            int right = nums.length - 1;
            while (curr <= right) {
                if (nums[mapping(curr)] > middle) {
                    swap(nums, mapping(curr), mapping(left));
                    curr++;
                    left++;
                } else if (nums[mapping(curr)] < middle) {
                    swap(nums, mapping(curr), mapping(right));
                    right--;
                } else {
                    curr++;
                }
            }
        }
        
        private void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
        
        private int mapping(int i) {
            return (i * 2 + 1) % (length | 1);
        }
        
        private int quickselect(int[] nums, int left, int right, int k) {
            if (left >= right) {
                return nums[left];
            }
            int position = partition(nums, left, right);
            if (position == k) {
                return nums[position];
            } else if (position < k) {
                return quickselect(nums, position + 1, right, k);
            } else {
                return quickselect(nums, left, position - 1, k);
            }
        }
        
        private int partition(int[] nums, int left, int right) {
            if (left >= right) {
                return left;
            }
            int value = nums[left];
            while (left < right) {
                while (left < right && nums[right] >= value) {
                    right--;
                }
                nums[left] = nums[right];
                while (left < right && nums[left] < value) {
                    left++;
                }
                nums[right] = nums[left];
            }
            nums[left] = value;
            return left;
        }
    }
    

Log in to reply
 

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