Java using Randomized Quick Selection


  • 0
    M
    public class Solution {
        public int minMoves2(int[] nums) {
            int mid = quickSelect(nums, nums.length / 2);
            return Arrays.stream(nums).map(i -> Math.abs(i - mid)).sum();
        }
        private static int quickSelect(int[] arr, int target) {
            int start = 0, end = arr.length - 1;
            while (start < end) {
                int q = randPartition(arr, start, end);
                if (q == target) return arr[q];
                if (target < q) end = q - 1;
                else start = q + 1;
            }
            return arr[start];
        }
        private static int randPartition(int[] arr, int p, int r) {
            if (p >= r) return p;
            int index = (int)(Math.random() * (r - p + 1) + p);
            swap(arr, index, r);
            int pivot = arr[r];
            int i = p - 1, j = p;
            while (j < r) {
                if (arr[j] <= pivot) swap(arr, ++i, j++);
                else j++;
            }
            swap(arr, ++i, r);     
            return i;
        }
        private static void swap(int[] arr, int p, int r) {
            int t = arr[p];
            arr[p] = arr[r];
            arr[r] = t;
        }
    }
    

    Hi guys, this is my solution using randomized quick selection algorithm, it is a theoretically O(n) algorithm, however it is slower than sorting the input array for given test cases. If the input size is really big, this algorithm should win.


Log in to reply
 

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