掘金 后端 ( ) • 2022-08-07 16:44

theme: devui-blue highlight: a11y-dark

携手创作,共同成长!这是我参与「掘金日新计划 · 8 月更文挑战」的第12天,点击查看活动详情

一、前言

二分搜索前提: 数据有序。

二分搜索重点在于细节,细节有二:

  1. 计算 mid 时需要防止溢出: 改写成 left + (right - left) / 2 则不会出现溢出。

    left + (right - left) / 2(left + right) / 2 的结果相同。 但如果 leftright 太大,直接相加会导致整型溢出。

  2. while(left <= right) while循环的条件中是 <= 还是 <

    使用 <= 还是 <,关键在于 (left, right) 区间问题? 为了统一,统一使用 <= 且 闭区间 [left, right]

# while(left <= right) 的终止条件是 left == right + 1
# 写出区间的形式:[right + 1, right]

# 举个栗子
[3, 2]

这时候说明区间已经为空了。

标准模板如下:

int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    return -1;
}

下面讨论两种二分搜索算法的变体: 寻找左侧边界的二分搜索 和 寻找右侧边界的二分搜索。

举个栗子:有个有序数组 nums= [1,3,3,3,4]target = 3

# 按标准二分搜索,会返回正中间的索引 2

# 如果想要得到 target 的左侧边界,即索引 1
# 如果想要得到 target 的右侧边界,即索引 3
# 就需要对二分搜索算法做一些改变。

二分搜索-2022-08-0616-38-26.png

寻找左侧边界的二分搜索模板:

int leftBinarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            // 别返回,收缩右边界,锁定左侧边界
            right = mid - 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }
    
    // 最后检查 left 越界的情况
    if (left >= nums.length || nums[left] != target) {
        return -1;
    }
    return left;
}

寻找右侧边界的二分搜索模板:

int rightBinarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            // 别返回,收缩左边界,锁定右侧边界
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }

    // 最后检查 right 越界的情况
    if (right < 0 || nums[right] != target) {
        return -1;
    }
    return right;
}

二、题目

(1)第一个出错的版本(易)

题干分析

这个题目说的是,给你一个整数 n,1 ~ n 表示一个产品的 n 个版本。其中,从某个版本开始,产品发生了错误。导致从那个版本开始,后面所有版本的产品都有问题。

现在给你一个函数 isBadVersion,输入一个版本号,它会告诉你这个版本的产品是否有问题。你要利用这个函数,找到第一个出错的版本。

# 比如说,给你的 n 等于 6,也就是说你要在 1 ~ 6 这 6 个版本中,找到第一个出错的版本。
# 假设第一个出错的版本为 4,那么调用 isBadVersion 会得到:

isBadVersion(1) => false
isBadVersion(2) => false
isBadVersion(3) => false
isBadVersion(4) => true
isBadVersion(5) => true
isBadVersion(6) => true

# 因此,对于这个例子,你要返回的第一个出错版本就是版本 4。

思路解法

思路:寻找左侧边界的二分搜索的变种

// Time: O(log(n)), Space: O(1), Faster: 34.00%
public int firstBadVersion(int n) {
    int left = 1, right = n;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (isBadVersion(mid)) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
}



(2)查找重复数字(中)

LeetCode 287

题干分析

这个题目说的是,给你一个大小为 n+1 的整数数组,数组中的数字都大于等于 1 并且小于等于 n。尝试证明数组中至少存在一个重复的数字。假设数组中只存在一个重复的数字,你要找出这个数字。

题目要求不能修改原数组,并且只能使用 O(1) 的辅助空间。

# 比如说,给你的数组是:
4, 3, 4, 1, 2, 5

# 这个数组的大小为 6,也就是说数组中每个数字都大于等于 1 并且小于等于 5。数组中重复的数字为 4,于是你要返回 4。

# 再比如说,给你的数组是:
1, 3, 3, 3

这个数组的大小为 4,也就是说数组中每个数字都大于等于 1 并且小于等于 3。数组中重复的数字是 3,于是你要返回 3。

思路分析

有个相似题: 只出现一次的两个数字 LeetCode260 ,可以用位操作(异或 ^,即 X ^ X = 0)。

这道题有些不同,但再难的题,也可以从暴力法出发,慢慢优化。

此题思路有三:

  1. 暴力法: 2 层 for 循环来查找。(会超出时间限制)
  2. 二分搜索变种:
  3. 双指针: 按下标走会得到一个环,LeetCode 94 单链表中圆环的开始节点

先来看暴力法,方法一:2 层for 循环。

// 方法一:暴力法
// Time: O(n^2), Space: O(1), Faster: 超出时间限制
public int findDuplicateBruteForce(int[] nums) {
    for (int i = 0; i < nums.length; ++i) {
        for (int j = i+1; j < nums.length; ++j) {
            if (nums[i] == nums[j]) return nums[i];
        }
    }

    return -1;
}

再来重点看下,方法二:二分搜索变种。

  • 重点在于: 统计,统计 <= 4 的数有几个?
    • 如果 <=4 的数有 5 个,那么重复的数就在 [1, 4] 之中。
    • 反之 ,重复的数就在 (4, n -1] 之中。

二分搜索-2022-08-0617-55-58.png

// 方法二: 二分搜索变种
// Time: O(n*log(n)), Space: O(1), Faster: 33.66%
public int findDuplicateBinarySearch(int[] nums) {
    int left = 1, right = nums.length - 1;
    while (left < right) {   // 重点
        int mid = left + (right - left) / 2;
        int count = 0;
        // 统计数量
        for (int num: nums) {
            if (num <= mid) ++count;
        }
        if (count > mid) right = mid;
        else left = mid + 1;
    }
    return left;
}

最后看下,方法三:双指针。

  1. 按数组的值索引走:会得到一个圆环。
  2. 找到圆环的开始节点,即为重复数字。

二分搜索-2022-08-0619-00-46.png

// 方法三: 双指针
// Time: O(n), Space: O(1), Faster: 93.12%
public int findDuplicateTwoPointer(int[] nums) {
    int slow = nums[0];
    int fast = nums[nums[0]];
    // 1. 快慢指针,相遇点
    while (slow != fast) {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }

    // 2. 临时指针从开始节点出发,找环的开始节点
    int p = 0;
    while (slow != p) {
        slow = nums[slow];
        p = nums[p];
    }
    return slow;
}



(3)最长递增子序列的长度(中)

LeetCode 300

题干分析

这个题目说的是,给你一个整数数组,你要计算数组里最长递增子序列的长度。其中,子序列不要求连续

# 比如说,给你的数组 a 是:
1, 8, 2, 6, 4, 5

# 在这个数组里,最长的递增子序列是:
1, 2, 4, 5

# 因此你要返回它的长度 4。

思路解法

思路有二: DP 和 二分搜索 + 堆

方法一:DP 动态规划

  • dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。
  • 推出 base case:dp[i] = 1 初始值为 1, 因为以 nums[i] 结尾的最长递增子序列起码要包含它自己。

二分搜索-2022-08-0623-19-46.png

// Time: o(n^2), Space: o(n), Faster: 27.93%
public int lengthOfLISDP(int [] nums) {
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length, max = 1;
    int [] dp = new int[n];
    dp[0] = 1;

    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            int cur = nums[i] > nums[j] ? dp[j] + 1 : 1;
            dp[i] = Math.max(dp[i], cur);
        }
        max = Math.max(max, dp[i]);
    }
    return max;
}

方法二:二分搜索 + 堆

二分搜索-2022-08-0623-31-36.png

  • 只能把点数小的牌压到点数比它大或者它相等的排上。
  • 如果当前牌点数较大没有可以放置的堆,则新建一个堆,再把这张牌放进去。
  • 如果当前牌有多个堆可以选择,则选择最左边那一堆放置。

步骤:

  1. 找位置: 二分搜索插入位置
  2. 把这张牌放到牌堆顶,没找到合适的牌堆,新建一堆

二分搜索-2022-08-0623-32-11.png

// Time: o(n * log(n)), Space: o(n), Faster:  99.60%
public int lengthOfLISBinarySearch(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    // 牌堆数初始化为 0
    int len = 0;
    int [] top = new int[nums.length]; // 记录牌顶的数字,即这个堆中最小的数字
    for (int x : nums) {
        int left = binarySearchInsertPosition(top, len, x);
        // 把这张牌放到牌堆顶
        top[left] = x;
        // 没找到合适的牌堆,新建一堆
        if (left == len) ++len;
    }
    return len;
}

private int binarySearchInsertPosition(int[] d, int len, int x) {
    int left = 0, right = len - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (x < d[mid]) right = mid - 1;
        else if (x > d[mid]) left = mid + 1;
        else return mid;
    }
    return left;
}



(4)求两个有序数组的中位数(难)

LeetCode 4

题干分析

这个题目说的是,给你两个排好序的整数数组 nums1nums2,假设数组是以递增排序的,数组的大小分别是 mn。你要找到这两个数组的中位数。要求算法的时间复杂度是 O(log(m+n))

这里两个数组中位数的意思是,两个数组合到一起排序后,位于中间的那个数,如果一共有偶数个,则是位于中间的两个数的平均数。

# 比如说,给你的两个数组是:
1, 3
2

# 它们放在一起排序后是:
1, 2, 3

# 所以中位数就是 2。


#再比如说,给你的两个数组是:
1, 3
2, 4


# 它们放在一起排序后是:
1, 2, 3, 4

# 所以中位数就是 (2 + 3) / 2 = 2.5。

思路解法

因为题目要求时间复杂度为 O(log(m+n)),那么就要缩小数据规模,采用二分搜索方式。

思路步骤如下:k = 4 表示两个数组中第四小的数

  • k 为奇数时,实际是从一个数组取 k / 2 个数,另一个数组取 k - k/2 个数

每一步排除 k / 2 个数,直到满足以下终止条件:

  1. k 减至 1, 那么第 1 小的数就是两个数组头部元素中较小的那个值。
  2. 把其中一个数组排除完,那么第 k 小的数就是直接从剩余那个数组取出即可。
public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
    int total = nums1.length + nums2.length;
    if ((total & 1) == 1) {
        return findKthSmallestInSortedArrays(nums1, nums2, total / 2 + 1);
    } else {
        double a = findKthSmallestInSortedArrays(nums1, nums2, total / 2);
        double b = findKthSmallestInSortedArrays(nums1, nums2, total / 2 + 1);
        return (a + b) / 2;
    }
}

// Time:o(log(k)) <= o(log(m + n)), Space: o(1), Faster: 100.00%
private double findKthSmallestInSortedArrays(int[] nums1, int[] nums2, int k) {

    int len1 = nums1.length, len2 = nums2.length, base1 = 0, base2 = 0;

    while (true) {

        if (len1 == 0) return nums2[base2 + k - 1];
        if (len2 == 0) return nums1[base1 + k - 1];
        if (k == 1) return Math.min(nums1[base1], nums2[base2]);

        int i = Math.min(k / 2, len1);
        int j = Math.min(k - i, len2);
        int a = nums1[base1 + i - 1], b = nums2[base2 + j - 1];

        if (i + j == k && a == b) return a;

        if (a <= b) {
            base1 += i;
            len1 -= i;
            k -= i;
        }

        if (a >= b) {
            base2 += j;
            len2 -= j;
            k -= j;
        }
    }
}