Java O(n) in worst case using median of medians


  • 0
    public class Solution {
        public void swap(int[] list, int i, int j) {
            int temp = list[i];
            list[i] = list[j];
            list[j] = temp;
        }
        public int partition(int[] list, int left, int right, int val) {
            int i;
            for (i = left; i < right; i++) {
                if (list[i] == val) {
                    break;
                }
            }
            swap(list, i, right);
            int pivotValue = list[right];
            int storeIndex = left;
            for (i = left; i <= right; i++) {
                if (list[i] < pivotValue) {
                    swap(list, storeIndex, i);
                    storeIndex++;
                }
            }
            swap(list, right, storeIndex);
            return storeIndex;
        }
        int findMedian(int arr[], int l, int len) {
            Arrays.sort(arr, l, l + len);
            return arr[l + len / 2];
        }
        int kthSmallest(int arr[], int l, int r, int k) {
            if (k > 0 && k <= r - l + 1) {
                int n = r - l + 1, i;
                int median[] = new int[(n + 4) / 5];
                for (i = 0; i < n / 5; i++) {
                    median[i] = findMedian(arr, l + i * 5, 5);
                }
                if (i * 5 < n) {
                    median[i] = findMedian(arr, l + i * 5, n % 5);
                    i++;
                }
                int medOfMed = (i == 1) ? median[i - 1]: kthSmallest(median, 0, i - 1, i / 2);
    
                int pos = partition(arr, l, r, medOfMed);
                if (pos - l == k - 1) {
                    return arr[pos];
                }
                if (pos - l > k - 1) {
                    return kthSmallest(arr, l, pos - 1, k);
                }
                return kthSmallest(arr, pos + 1, r, k - pos + l - 1);
            }
            return Integer.MAX_VALUE;
        }
        public int minMoves2(int[] nums) {
            int sum = 0;
            int median = kthSmallest(nums, 0, nums.length - 1, nums.length / 2 + 1);
            for (int num : nums) {
                sum += Math.abs(median - num);
            }
            return sum;
        }
    }

Log in to reply
 

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