AllenY's blog

🧑🏻‍💻🎮🍿🎹🗻

Home Archive Tags About

LeetCode刷题记录（二分查找篇）

2024-11-12 11 min read # LeetCode

LeetCode刷题记录（二分查找篇），个人向。

[35] Search Insert Position

难度：Easy
语言：C++

题目描述。
基本的二分查找，在此基础上增加了一个寻找插入位置（即使不存在，也应该返回可以插入的位置）。此类题目注意循环不变量即可，例如以下代码坚持了左闭右开[left, right)的写法。

class Solution {
  public:
    int searchInsert(vector<int> &nums, int target) {
        int left = 0;
        int right = nums.size();
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }
};

[74] Search a 2D Matrix

难度：Medium
语言：C++

题目描述。
两次二分查找，没什么好说的。需要注意第一次查找的结果是down - 1。
还有一种解法是把矩阵拉平，即把矩阵的几行拼起来成一行数组，然后直接在数组上做一次二分查找。可参考这篇solution。

class Solution {
  public:
    bool searchMatrix(vector<vector<int>> &matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int up = 0;
        int down = m;
        int row = 0;
        while (up < down) {
            row = up + (down - up) / 2; // To avoid overflow
            if (target == matrix[row][0]) {
                return true;
            } else if (target < matrix[row][0]) {
                down = row;
            } else {
                up = row + 1;
            }
        }
        row = down - 1;
        if (row < 0) {
            return false;
        }
        int left = 0;
        int right = n;
        while (left < right) {
            int col = left + (right - left) / 2;
            if (target == matrix[row][col]) {
                return true;
            } else if (target < matrix[row][col]) {
                right = col;
            } else {
                left = col + 1;
            }
        }
        return false;
    }
};

[34] Find First and Last Position of Element in Sorted Array

难度：Medium
语言：C++

题目描述。
先尝试自己写了一种解法。先用二分查找找到target，再在该数字左边（包括该数字）用二分查找找到最左的target（即左边的数字不等于target），同理再找到最右的target，最后返回即可。但该代码太过繁琐冗长。
另一种解法的核心是，通过调整nums[mid] == target时是应该调整左边界还是右边界，来找到target的左边界和右边界，最后返回即可。

class Solution {
  public:
    vector<int> searchRangeDivide(vector<int> &nums, int target) {
        int size = nums.size();
        if (size == 0) {
            return vector<int>(2, -1);
        }
        int left = 0, right = size;
        int mid = 0;
        vector<int> result;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                break;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[mid] != target) {
            result.assign(2, -1);
            return result;
        }

        if (mid == 0 || nums[mid - 1] != target) {
            result.push_back(mid);
        } else {
            int left_left = 0, left_right = mid + 1;
            while (left_left < left_right) {
                int left_mid = left_left + (left_right - left_left) / 2;
                if (nums[left_mid] == target &&
                    (left_mid == 0 || nums[left_mid - 1] != target)) {
                    result.push_back(left_mid);
                    break;
                } else if (nums[left_mid] >= target) {
                    left_right = left_mid;
                } else {
                    left_left = left_mid + 1;
                }
            }
        }

        if (mid == size - 1 || nums[mid + 1] != target) {
            result.push_back(mid);
        } else {
            int right_left = mid, right_right = size;
            while (right_left < right_right) {
                int right_mid = right_left + (right_right - right_left) / 2;
                if (nums[right_mid] == target &&
                    (right_mid == size - 1 || nums[right_mid + 1] != target)) {
                    result.push_back(right_mid);
                    break;
                } else if (nums[right_mid] <= target) {
                    right_left = right_mid + 1;
                } else {
                    right_right = right_mid;
                }
            }
        }

        return result;
    }

    int findTarget(const vector<int> &nums, int target, bool left_flag) {
        int left = 0, right = nums.size();
        int border = -1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                border = mid;
                if (left_flag) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return border;
    }

    vector<int> searchRange(vector<int> &nums, int target) {
        int left = findTarget(nums, target, true);
        int right = findTarget(nums, target, false);
        if (left == -1 || right == -1) {
            return {-1, -1};
        } else if (right >= left) {
            return {left, right};
        } else {
            return {-1, -1};
        }
    }
};

[33] Search in Rotated Sorted Array

难度：Medium
语言：C++

题目描述。
判断first即nums[0]与target和nums[mid]三者之间的大小关系即可。nums[mid] < target的情况下，可能target比first大，即target在左边的递增序列部分，而nums[mid]在右边的序列部分，此时应该调整右指针而不是左指针。同理，target <= nums[mid]的情况也有可能是first ... nums[mid] ... target这样的排列，此时应该调整左指针而不是右指针。
另一种思考方式是，先考虑nums[mid]和first之间的大小关系，从而得知是nums[mid]左边有序还是右边有序，然后根据target是否落在该有序部分来决定是该搜索mid左边还是右边。具体可参考这篇solution。

class Solution {
  public:
    int search(vector<int> &nums, int target) {
        int left = 0;
        int right = nums.size();
        int first = nums[0];
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                if (first <= target &&
                    first >= nums[mid]) { // first ... target ... nums[mid]
                    right = mid;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target < first &&
                    nums[mid] >= first) { // first ... nums[mid] ... target
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
        }

        return -1;
    }
};

[153] Find Minimum in Rotated Sorted Array

难度：Medium
语言：C++

题目描述。
判断nums[mid]与右边界元素即nums[right]之间的大小关系。如果nums[mid] < nums[right]，则说明nums[mid]在数组右边递增部分（较小部分），最小值索引在[left, mid]之间，可调整右指针使查找范围靠左；反之则调整左指针使查找范围靠右。由于是闭区间，最终会left == right即区间长度为一，此时返回结果即可。

class Solution {
  public:
    int findMin(vector<int> &nums) {
        int left = 0;
        int right = nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return nums[right];
    }
};

[4] Median of Two Sorted Arrays

难度：Hard
语言：C++

题目描述。
较有挑战性的一道题目。即使知道大概的算法，实际实现时也要注意各种边界条件的处理等。

  • 首先，我们假设nums1的长度不长于nums2。如果不满足，就交换一下nums1和nums2即可。

  • 我们想找到一个划分，该划分把nums1和nums2各自分为了左右部分，我们可以称其为nums1_left_part, nums1_right_part, nums2_left_part和nums2_right_part。该划分满足：

    • 如果总长度m + n为偶数，则划分左部分（即nums1_left_part与nums2_left_part）长度之和与右部分相等；若为奇数，则左部分数量比右部分多1。
    • 左部分的所有元素均不大于右部分的所有元素。

    当我们找到了这样的一个划分，中位数就是左部分的最大元素和右部分的最小元素的平均值（或者就是左边的最大元素，取决于m + n是否为奇数）。

  • 我们可以通过二分查找的方式来找到这个划分的位置。先使用二分查找找到nums1中的划分位置i，然后以此作为自变量，把nums2对应的划分位置j作为因变量，通过i + j = (m + n + 1) / 2的方式把j算出来。+1是为了保证左半部分元素的数量大于等于右半部分的数量（如果是偶数，没有影响；如果是奇数，则左边比右边多1）。

  • 然后，我们比较划分左右的四个元素，接着比较nums1[i-1]和nums2[j]的大小。若满足nums1[i-1] <= nums2[j]，则记录此时左边最大值和右边最小值，然后更新左指针（尝试从nums1的更右边去划分）；否则，更新右指针（说明nums1划分得太靠右了，需要往左划分来减小nums1[i-1]的值同时增大nums2[j]的值）。这样，我们会找到一个最大的i使得nums1[i-1] <= nums2[j]，此时也会自动满足nums2[j-1] <= nums1[i]，这是因为i已经是最大的，说明i+1不满足，说明nums1[i] >= nums2[j-1]，就正好是第二个公式。这样一来，我们找到了划分的位置，在保证左右元素数量相等（或左边多一）的同时使左边的所有元素均不大于右边的所有元素。

  • 最后，根据m + n是否是偶数，返回左边最大值(median1)与右边最小值(median2)的平均值或直接返回median1即可。

class Solution {
  public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {
        if (nums1.size() > nums2.size()) {
            // to make sure that nums1.size() <= nums2.size()
            return findMedianSortedArrays(nums2, nums1);
        }

        int m = nums1.size();
        int n = nums2.size();
        int left = 0, right = m;
        int median1 = 0, median2 = 0;

        while (left <= right) {
            int i = (left + right) / 2;
            // i + j = (m + n + 1) / 2
            int j = (m + n + 1) / 2 - i;

            int nums_im1 = (i == 0 ? INT_MIN : nums1[i - 1]);
            int nums_i = (i == m ? INT_MAX : nums1[i]);
            int nums_jm1 = (j == 0 ? INT_MIN : nums2[j - 1]);
            int nums_j = (j == n ? INT_MAX : nums2[j]);

            if (nums_im1 <= nums_j) {
                median1 = max(nums_im1, nums_jm1);
                median2 = min(nums_i, nums_j);
                left = i + 1;
            } else {
                right = i - 1;
            }
        }

        return (m + n) % 2 == 0 ? (median1 + median2) / 2.0 : median1;
    }
};

总结

定义左边界left和右边界right，然后判断mid与目标target之间的大小关系，以此来更新左边界或者右边界，应该是二分查找类题的基础模版。需要注意的是，需要约定好左边界和右边界分别是开区间还是闭区间，然后在实现时始终遵守这一点。例如本人习惯定义[left, right)，则while循环的条件应该是left < right而不是left <= right。

33和153都涉及到了Rotated Sorted Array。这里可以通过对比mid与array第一个元素或最后一个元素的大小关系来得知mid处于哪一段有序序列中，以此信息来调整left或right。

最后的4是较有难度的题。这里我们先确保nums1.size() <= nums2.size()，然后使用二分查找的方式找到nums1中的划分位置i，并以此为自变量计算出nums2中的划分位置出j。我们通过比较划分左右四个元素的大小关系（实际只需要比较两个即nums1[i-1]和nums2[j])来更新左或右指针，直到找到最大的i使得nums1[i-1] <= nums2[j]，此时直接计算出中位数即可（(median1 + median2) / 2.0或median1）。

Copyright © 2023-2024 Allen Yuan. All rights reserved. RSS