Easy To Understand Java AC Without Using Virtue Index


  • 0
    G
    public void wiggleSort(int[] nums) {
            if (nums.length == 0) return;
            int median = findKthLargest(nums, (nums.length + 1) / 2);
            int odd = 1;
            int even = nums.length % 2 == 0? nums.length - 2 : nums.length - 1;
            int[] temp = new int[nums.length];
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] > median) {
                    temp[odd] = nums[i];
                    odd += 2;
                }
                else if (nums[i] < median) {
                    temp[even] = nums[i];
                    even -= 2;
                }
            }
            while (odd < nums.length) {
                temp[odd] = median;
                odd += 2;
            }
            while (even>=0) {
                temp[even] = median;
                even -= 2;
            }
            for (int i = 0; i < nums.length; i++) nums[i] = temp[i];
        }
        
        public int findKthLargest(int[] a, int k) {
            int n = a.length;
            return quickSelect(a, 0, n - 1, n - k + 1);
        }
      
        public int quickSelect(int[] a, int lo, int hi, int k) {
            int i = lo, j = hi, pivot = a[hi];
            while (i < j) {
                if (a[i++] > pivot) swap(a, --i, --j);
            }
            swap(a, i, hi);
            
            int m = i - lo + 1;
            if (m == k) return a[i];
            else if (m > k) return quickSelect(a, lo, i - 1, k);
            else return quickSelect(a, i + 1, hi, k - m);
        }
    
        public void swap(int[] a, int i, int j) {
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }

Log in to reply
 

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