专题【二分查找】刷题日记

🕗 发布于 2024-04-21 13:09 算法

题目列表

4. 寻找两个正序数组的中位数
 33. 搜索旋转排序数组
 34. 在排序数组中查找元素的第一个和最后一个位置
 35. 搜索插入位置
 69. x 的平方根
 167. 两数之和 II - 输入有序数组
 209. 长度最小的子数组
 222. 完全二叉树的节点个数
 287. 寻找重复数

2023.04.14

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

题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

思路

总元素个数如果是奇数
每一个数组都找中间的指针
如果对于这俩指针，左右恰巧数量一样，就返回这俩指针对应的元素（奇数返回小的，偶数返回两个的平均）
a[0], …, a[i],…a[m-1]，b[0],…,b[j],…b[n-1]，左右一样指a[0]…a[i]元素个数加上b[0]…b[j]元素个数和剩余部分一致，并且a[i-1]<b[j]<a[i+1] && b[j-1] < a[i] < b[j+1]，即a[i]的坐边小于b[j]、b[j]的左边小于a[i]、a[i]的右边大于b[j]、b[j]的右边大于a[i]
否则使用二分查找其中一个，同时调整另一个元素的个数，始终保持，左右元素相等，直到满足上述第二个条件

答案

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;

        if (m > n) {
        // 从短的做遍历。为了避免处理nums2的边界
            return findMedianSortedArrays(nums2, nums1);
        }
        int halfNum = (m + n + 1) / 2;

        int left = 0, right = m;
        int leftMax = 0, rightMin = 0;

        while (left <= right) {
        // 防溢出
            int middle1 = left + (right - left) / 2;
            int middle2 = halfNum - middle1;

// i_1要处理左溢出即==0的判断，i本身要处理右溢出即==m
// MAX_VALUE还是MIN_VALUE是从max还是min赋值的，反正就是取合法的那边
            int ai_1 = middle1 == 0 ? Integer.MIN_VALUE : nums1[middle1 - 1];
            int ai = middle1 == m ? Integer.MAX_VALUE : nums1[middle1];

            int bj_1 = middle2 == 0 ? Integer.MIN_VALUE : nums2[middle2 - 1];
            int bj = middle2 == n ? Integer.MAX_VALUE : nums2[middle2];

// 满足条件就记录
            if (ai_1 <= bj) {
                leftMax = Math.max(ai_1, bj_1);
                rightMin = Math.min(ai, bj);
                left = middle1 + 1;
            } else {
                right = middle1 - 1;
            }

        }
        // 满足条件才更新，所以直接返回
        return ((m + n) % 2 == 0) ? (leftMax + rightMin) / 2.0 : leftMax;

    }
}

33. 搜索旋转排序数组

题目

整数数组 nums 按升序排列，数组中的值互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]]（下标从 0 开始计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

示例 3：

输入：nums = [1], target = 0
输出：-1

提示：

1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums 中的每个值都独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104

思路

核心是找到在哪边搜索

先判断哪边是有序的
如果目标值在有序的这边，就在这边，否则在另一边

答案

class Solution {
    public int search(int[] nums, int target) {
        return search(nums, target, 0, nums.length - 1);
    }

    public int search(int[] nums, int target, int left, int right) {
    // 递归的边界
        if (left > right) {
            return -1;
        }

        int middle = left + (right - left) / 2;
        int value = nums[middle];
        // 递归的终止条件
        if (value == target) {
            return middle;
        } 
        // 左边有序
        if (nums[left] <= value) {
        // 因为左边有序，所以判断在不在左边范围内，在的话就在左边
            if (target < value && nums[left] <= target) {
                return search(nums, target, left, middle - 1);
            } else {
                return search(nums, target, middle + 1, right);
            }
        } else {
        // 右边同理
            if (target > value && target <= nums[right]) {
                return search(nums, target, middle + 1, right);
            } else {
                return search(nums, target, left, middle - 1);
            }
        }
    }
}

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

题目

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

思路

和普通二分的区别是搜索到之后的动作

搜索最左边的话，就一直把右边界往左边移动。
右边同理，详见注释

答案

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if (nums.length == 0) {
            return new int[] { -1, -1 };
        }
        return new int[] { lBsearch(nums, target, 0, nums.length - 1), rBsearch(nums, target, 0, nums.length - 1) };
    }

    public int lBsearch(int[] nums, int target, int left, int right) {
// 因为左右都是闭区间，所以相等
        while (left <= right) {
            int middle = left + (right - left) / 2;
            int value = nums[middle];
            if (value < target) {
                left = middle + 1;
            } else {
            // 相等就移动右边界
                right = middle - 1;
            }
        }
        // 考虑剩两个元素的时候，[m, target]，这时候middle==left, m < target，最后右移一步。所以最后，如果有left一定指向元素
        // 考虑剩两个元素的时候，[target, target]，这时候middle==left, 最后左移一步。所以最后，如果有left一定指向元素
        // 一些边界判断
        return left >= 0 && left < nums.length && nums[left] == target ? left : -1;
    }

// 同搜索左边界
    public int rBsearch(int[] nums, int target, int left, int right) {
        while (left <= right) {
            int middle = left + (right - left) / 2;
            int value = nums[middle];
            if (value <= target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return right >= 0 && right < nums.length && nums[right] == target ? right : -1;
    }
}

2024.04.19

35. 搜索插入位置

题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 为无重复元素的升序排列数组
-104 <= target <= 104

思路

比二分查找，要多考虑下，最后left和right的位置关系
考虑两个元素的时候[m, n], m < target < n, nums[middle] = m < target，移动right，left和right重合在m，最后一次，right-1，left不动

答案

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        // 闭区间，所以=
        while (left <= right) {
            int middle = left + (right - left) / 2;
            int value = nums[middle];

            if (value == target) {
                return middle;
            } else if (value < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return left;
    }
}

69. x 的平方根

题目

给你一个非负整数 x ，计算并返回 x 的算术平方根。
由于返回类型是整数，结果只保留整数部分，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842…, 由于返回类型是整数，小数部分将被舍去。

提示：

0 <= x <= 2^31 - 1

思路

0-x一半一半逼近，因为1 = 1 x 1, 所以x是闭区间

答案

class Solution {
    public int mySqrt(int x) {
    // 边界0,1
        if (x < 2) {
            return x;
        }
        int left = 0, right = x;

        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (x / middle == middle) {
                return middle;
            } else if (x / middle < middle) {
                right = middle - 1;
            } else {
                left = middle + 1;
            }
        }
        // 2.8取2，所以-1
        return left - 1;
    }
}

167. 两数之和 II - 输入有序数组

题目

给你一个下标从 1 开始的整数数组 numbers ，该数组已按非递减顺序排列，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

提示：

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按非递减顺序排列
-1000 <= target <= 1000
仅存在一个有效答案

思路

因为有序，固定一个，另一个用二分

答案

// 二分，O（n log(n)）
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            int current = numbers[i];
            int left = i + 1;
            int right = numbers.length - 1;
            while (left <= right) {
                int middle = left + (right - left) / 2;
                if (current + numbers[middle] == target) {
                    return new int[] { i + 1, middle + 1 };
                } else if (current + numbers[middle] < target) {
                    left = middle + 1;
                } else {
                    right = middle - 1;
                }
            }
        }
        return new int[] { -1, -1 };
    }
}
// 双指针 O(n)
class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int leftValue = numbers[left];
            int rightValue = numbers[right];
            if (leftValue + rightValue == target) {
                return new int[] { left + 1, right + 1 };
            } else if (leftValue + rightValue < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[] { -1, -1 };
    }
}

209. 长度最小的子数组

题目

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的连续
子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

进阶：

如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

思路

滑动窗口
前缀和+二分搜索。二分一定要有序，前缀和可以做到

答案

// 滑动窗口
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        int left = 0, right = 0;
        int sum = 0;
        while (right < nums.length) {
            sum += nums[right];

            while (sum >= target && left <= right) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
            right++;

        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}
// 前缀和+二分
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int[] sums = new int[nums.length + 1];
        int sum = 0;
        for (int i = 1; i < sums.length; i++) {
            sum += nums[i - 1];
            sums[i] = sum;
        }

        int result = Integer.MAX_VALUE;
        for (int i = 0; i < sums.length; i++) {
            int current = sums[i];
            int left = i + 1, right = sums.length - 1;
            while (left <= right) {
                int middle = left + (right - left) / 2;
                int value = sums[middle];
                if (value - current >= target) {
                    result = Math.min(result, middle - i);
                    right = middle - 1;
                } else {
                    left = middle + 1;
                }
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

222. 完全二叉树的节点个数

题目

给你一棵完全二叉树的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。

示例 1：
在这里插入图片描述

输入：root = [1,2,3,4,5,6]
输出：6

示例 2：

输入：root = []
输出：0

示例 3：

输入：root = [1]
输出：1

提示：

树中节点的数目范围是[0, 5 * 104]
0 <= Node.val <= 5 * 104
题目数据保证输入的树是完全二叉树

进阶： 遍历树来统计节点是一种时间复杂度为 O(n) 的简单解决方案。你可以设计一个更快的算法吗？

思路

因为是完全二叉树
求左右树的高度，如果相等，则说明左子树是完全二叉树，左子树元素个数是2^{左子树的高度}-1，再加上根节点，就是2^{左子树的高度}
如果不相等，说明右子树是完全二叉树，算法同2

答案

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = high(root.left);
        int right = high(root.right);

        if (left == right) {
        // 左子树是完全二叉树，左子树加右边的数量
            return countNodes(root.right) + (1 << left);
        } else {
        // 右子树是完全二叉树，右子树加左边的数量
            return countNodes(root.left) + (1 << right);
        }
    }

    public int high(TreeNode root) {
        int result = 0;
        while (root != null) {
            result++;
            root = root.left;
        }
        return result;
    }
}

287. 寻找重复数

题目

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。
假设 nums 只有一个重复的整数，返回这个重复的数。
你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。

示例 1：

输入：nums = [1,3,4,2,2]
输出：2

示例 2：

输入：nums = [3,1,3,4,2]
输出：3

示例 3 :

输入：nums = [3,3,3,3,3]
输出：3

提示：

1 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
nums 中只有一个整数出现两次或多次，其余整数均只出现一次

进阶：

如何证明 nums 中至少存在一个重复的数字?
你可以设计一个线性级时间复杂度 O(n) 的解决方案吗？

思路

之前双指针有过，这次换个思路
要二分，必须有单调数组，有点像定义DP数组了、本次定义cnt[i]表示小于等于i的元素数量，有点像前缀和的逻辑，记住吧。数组构造单调数组有两个办法：前缀和、cnt[i]
如果数组中只有一个重复元素，根据题意 nums.length == n + 1 、1 <= nums[i] <= n，其实必然重复（n+1个位置，只有n个元素）。则重复元素之前，cnt[i] == i，[1,2,3,4,5,6,5,7,8]，这种cnt[0-4] = [0-4]，因为可能重复多个，所以cnt[i] <= i
用二分找到这个就行了，就是哪个位置开始出现不小于等于

答案

class Solution {
    public int findDuplicate(int[] nums) {
        int left = 0, right = nums.length - 1;
        int result = 0;
        // 找数，数在0-n之间（根据题意nums.length==n+1），搜索的是小于等于xxx
        while (left <= right) {
        // 二分找数
            int middle = left + (right - left) / 2;
            // 计算cnt
            int cnt = 0;
            for (int i = 0; i < nums.length; i++) {
            // 遍历数组，小于等于middle的数个数
                if (nums[i] <= middle) {
                    cnt++;
                }
            }
            // 是不是满足条件，满足说明数小了
            if (cnt <= middle) {
                left = middle + 1;
            } else {
            // 记录下，因为可能是大于target的，所以继续搜索
            // [1,2,3,4,5,6,5,7,8]，cnt[6] = 7, cnt[5] = 6, cnt[8] = 8，都满足条件，所以继续搜索
                result = middle;
                right = middle - 1;
            }
        }
        return result;
    }
}

原文地址：https://blog.csdn.net/LaMole_Ryouji/article/details/137709997

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Springboot+Vue项目-基于Java+MySQL的蜗牛兼职网系统(附源码+演示视频+LW)
下一篇：[USACO1.5] 八皇后 Checker Challenge

linux线程cp模型，posix信号量，线程池，线程封装，单例模型，懒汉饿汉实现方式，自旋锁，读者写者模型
前面的同步，我们并没有一个很好的场景来模拟同步，只是简单的将有序的现象输出出来；现在我们来讲解一个比较合理且常见的模型——生产者消费者模型；
阅读更多2024-09-07
Qt/C++开源项目 TCP服务器调试助手（源码分享+发布链接下载）
该TCP服务器调试助手是用于测试和监控基于TCP协议的网络通信工具，能够帮助开发者便捷地进行网络通信调试。通过简洁的界面设计，用户可以轻松配置、管理TCP端口的连接，收发消息并进行数据监控分析。123
阅读更多2024-09-07
vue3整合antv x6实现图编辑器快速入门
例如：在上面节点基础上，我们有一个新的需求：给节点加上右键菜单。X6 支持使用 SVG、HTML 来渲染节点内容，在此基础上，我们还可以使用 React、Vue 组件来渲染节点，这样在开发过程中会非常
阅读更多2024-09-07
linux使用samba共享目录，其他虚拟机和windows都可以访问
linux使用samba共享目录，其他虚拟机和windows都可以访问
阅读更多2024-09-07
Linux系统编程实现ls -l | wc -l指令
由于该指令是通过管道的形式实现的，所以我们要使用系统函数pipe。ls -l |wc -l的作用就是统计当前目录有多少文件。由于父子间通过管道实现，所以存在读写阻塞问题，不用担心僵尸进程的产生，所以可
阅读更多2024-09-07
MySQL表操作及约束
MySQL表操作及约束
阅读更多2024-09-07
1.2CubeMAX创建FREERTOS入门示例
内核参数设置，用户根据自己的实际应用来裁剪定制。：相关宏的定义，可以自建一些常量在工程中使用。User Constants（用户常量）：定时器和信号量的创建。：用于查看堆使用情况。：任务与队列
阅读更多2024-09-07
YOLOv9改进策略【注意力机制篇】| PSA极化自我关注：实现高质量像素回归
本文记录的是基于PSA注意力模块的YOLOv9目标检测方法研究。PSA模块。本文将其应用到YOLOv9的检测任务中，使模型能够更好地捕捉图像中的细节信息，以实现目标检测任务中准确识别和定位。
阅读更多2024-09-07
爆改YOLOv8|利用yolov10的SCDown改进yolov8-下采样
yolov8改进，yolov10, 下采样SCDown, 即插即用
阅读更多2024-09-07
PDF样本图册转换为一个链接，随时打开无需印刷
想象一下，您手中有一本厚重的样本图册，里面包含了丰富多样的内容，如产品介绍、项目方案、学术论文等。在过去，您需要逐一翻阅、筛选，甚至为了便于查看，不得不将其印刷出来。如今，借助先进的数字化技术，还能实
阅读更多2024-09-07

专题【二分查找】刷题日记

题目列表

2023.04.14

题目

思路

答案

题目

思路

答案

题目

思路

答案

2024.04.19

题目

思路

答案

题目

思路

答案

题目

思路

答案

题目

思路

答案

题目

思路

答案

题目

思路

答案

相关文章