LeetCode Hot100 BS

Posted on Edited on

搜索插入位置

Problem

https://leetcode.cn/problems/search-insert-position/?envType=study-plan-v2&envId=top-100-liked

Solution

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {

        int n = nums.size();

        int l = 0, r = n-1;

        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (nums[mid] < target)
            {
                l = mid + 1;
            }
            else if (nums[mid] > target)
            {
                r = mid - 1;
            }
            else
            {
                return mid;
            }
        }
        return l;
    }
};

搜索二维矩阵

Problem

https://leetcode.cn/problems/search-a-2d-matrix/description/?envType=study-plan-v2&envId=top-100-liked

Solution

将二维矩阵看成升序的一位数组，二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();

        int l = 0, r = m * n - 1;

        while (l <= r)
        {
            int mid = (l + r) / 2;
            int row = mid / n;
            int col = mid % n;

            if (matrix[row][col] < target)
            {
                l = mid + 1;
            }
            else if (matrix[row][col] > target)
            {
                r = mid - 1;
            }
            else
            {
                return true;
            }
        }
        return false;


    }
};

在排序数组中查找元素的第一个和最后一个位置

Problem

https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/?envType=study-plan-v2&envId=top-100-liked

Solution

使用两遍二分查找，第一遍找第一个位置，每次遇到target移动右边界并记录当前索引，第二遍找最后一个位置，每次遇到target移动左边界并记录当前索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        int first = -1, second = -1;
        int l = 0, r = n - 1;
        while (l <= r)
        {
            int mid = (l + r) / 2;

            if (nums[mid] > target)
            {
                r = mid-1;
            }
            else if (nums[mid] < target)
            {
                l = mid+1;
            }
            else
            {
                r = mid-1;
                first = mid;
            }
        }

        l = 0;
        r = n-1;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (nums[mid] > target)
            {
                r = mid-1;
            }
            else if (nums[mid] < target)
            {
                l = mid+1;
            }
            else
            {
                l = mid+1;
                second = mid;
            }
        }
        return {first, second};
    }
};

搜索旋转排序数组

Problem

https://leetcode.cn/problems/search-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-100-liked

Solution

二分查找，如果当前区间升序则直接使用正常的二分查找，否则判断mid和target是否在同一个升序范围，若在则使用普通的二分查找，若不在则根据target在分界点的左边还是右边来缩小范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    int search(vector<int>& nums, int target) {

        int n = nums.size();
        int l = 0, r = n-1;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (nums[mid] == target)
            {
                return mid;
            }

            if (nums[l] < nums[r])
            {
                if (nums[mid] < target)
                {
                    l = mid + 1;
                }
                else
                {
                    r = mid - 1;
                }
            }
            else
            {
                if (nums[mid] >= nums[l] ^ target >= nums[l])
                {
                    if (target < nums[l])
                    {
                        l = mid + 1;
                    }
                    else
                    {
                        r = mid - 1;
                    }
                }
                else
                {
                    if (target < nums[mid])
                    {
                        r = mid - 1;
                    }
                    else
                    {
                        l = mid + 1;
                    }
                }
            }
        }
        return -1;
    }
};

寻找旋转排序数组中的最小值

Problem

https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/?envType=study-plan-v2&envId=top-100-liked

Solution

二分查找，如果当前区间升序nums[l] < nums[r]则nums[l]即为所求，否则判断mid的位置，若nums[mid]小于等于nums[r]说明最小值在[l, mid]中，否则在(mid-r]中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findMin(vector<int>& nums) {
        int n = nums.size();
        int l = 0, r = n - 1;

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

            if (nums[l] <= nums[r])
                return nums[l];

            if (nums[mid] <= nums[r])
                r = mid;
            else
                l = mid+1;
        }
        return nums[l];
    }
};

寻找两个正序数组的中位数

Problem

https://leetcode.cn/problems/median-of-two-sorted-arrays/description/?envType=study-plan-v2&envId=top-100-liked

Solution

找两个正序数组中的中位数，例如[1, 2],[3, 4]，相当于找第2个数和第3个数的平均值。定义在两个升序数组中找第k个数的函数（k从1开始）。
见注释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:

    int getKthNum(const vector<int> &nums1, int l1, const vector<int> &nums2, int l2, int k)
    {
        int n1 = nums1.size();
        int n2 = nums2.size();

        if (l1 >= n1) return nums2[l2 + k - 1];
        if (l2 >= n2) return nums1[l1 + k - 1];
        if (k == 1) return min(nums1[l1], nums2[l2]);

        int mid1 = min(l1 + k/2-1, n1-1); // 在nums1[l1:]中定位第k/2个数，不足k/2定位到最后一个数
        int mid2 = min(l2 + k/2-1, n2-1); // 在nums2[l2:]中定位第k/2个数，不足k/2定位到最后一个数
        int ans = 0;

        if (nums1[mid1] < nums2[mid2])
        { // 如果nums1中的数小，小于它的数最大只可能有k/2+k/2-2个（不含它自己），说明第k个数不可能出现在[l1, mid1]中
            ans = getKthNum(nums1, mid1+1, nums2, l2, k - (mid1 - l1 + 1));
        }
        else
        { // 同理，如果nums2中的数小，说明第k个数不可能出现在[l2, mid2]中
            ans = getKthNum(nums1, l1, nums2, mid2+1, k - (mid2 - l2 + 1));
        }
        return ans;
    }

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size();
        int n2 = nums2.size();

        int len = n1 + n2;
        if (len & 1)
        {
            return getKthNum(nums1, 0, nums2, 0, (len+1) / 2);
        }
        else
        {
            return ((double)getKthNum(nums1, 0, nums2, 0, len / 2) + getKthNum(nums1, 0, nums2, 0, len / 2 + 1)*1.0f) / 2.0;
        }
        return 0.0;
    }
};