2616. Minimize the Maximum Difference of Pairs - Medium

前往題目

想法

• Binary Search
• 搜尋diff

思路

1. 二元搜尋最小的最大差
2. 如果這個差invalid就往大的找
3. 如果valid就往更小的試
4. 判斷是否valid只要搜尋整個陣列，pair by pair如果找到比當前搜尋的差還小或相等，而且滿足目標對數(pairs)，那就回傳true，否則就代表這個差太小了，要往更大的找

Code

第一次寫的思路幾乎一樣，但在判斷valid的條件時有點小bug，忘了用到diff

class Solution {
    public int minimizeMax(int[] nums, int p) {
        if (p == 0) return 0;

        Arrays.sort(nums);

        int l = 0, r = (int) Math.pow(10, 9);
        int res = (int) Math.pow(10, 9);

        while (l <= r) {
            int mid = l + (r - l) / 2;

            if (isValid(nums, p, mid)) {
                res = mid;
                r = mid - 1; // Search for smaller diff.
            } else {
                l = mid + 1; // Try for bigger diff
            }
        }
        return res;
    }

    private boolean isValid(int[] nums, int p, int diff) {
        int i = 0, count = 0;

        // Go through nums, pair by pair
        while (i < nums.length - 1) {
            // Found valid pair
            if (Math.abs(nums[i] - nums[i + 1]) <= diff) {
                ++count;
                i += 2; // Move to another pair
            } else {
                ++i; // In case the second number could be in the next pair
            }

            // Found enough pair
            if (count == p) return true;
        }
        return false;
    }
}

▶

Failed Attempt

class Solution {
    int res = 0;

    public int minimizeMax(int[] nums, int p) {
        int smallest = Integer.MAX_VALUE, secSmallest = 0, largest = Integer.MIN_VALUE;

        // Find smallest and largest num
        for (int num : nums) {
            smallest = Math.min(smallest, num);
            largest = Math.max(largest, num);
        }

        // Find the second smallest num
        for (int num : nums) {
            if (num == smallest) continue;
            secSmallest = Math.min(secSmallest, num);
        }

        // Define upper bound and lower bound
        int l = secSmallest - smallest, r = largest;


        Arrays.sort(nums);

        // Start binary search
        while (l <= r) {
            int mid = l + (r - l) / 2;
            
            // Valid, so check even smaller diff
            if (isValid(nums, p, mid) >= 0) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }

    private int isValid(int[] nums, int p, int diff) {
        int max = -1;

        for (int i = 0, pCounter = 0; i < nums.length && pCounter < p; i += 2, pCounter++) {
            max = Math.max(max, Math.abs(nums[i] - nums[i + 1]));
        }
        if (max > -1) {
            res = Math.max(res, max);
        }
        return max;
    }
}