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

🕗 发布于 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

Web性能优化：从基础到高级
然而，要充分发挥性能优化的潜力，还需要持续监测和逐步优化，确保每一步都符合用户体验的要求。企业级应用通常包含复杂的业务逻辑和大量的数据交互，通过优化 CSS 和 JavaScript，避免阻塞渲染，可
阅读更多2024-11-15
HTML5+CSS前端开发【保姆级教学】＋前端介绍和软件安装
前端开发主要涉及网站和 App，用户能够从 App 屏幕或浏览器上看到东西。能够从 App 屏幕和浏览器上看到的东西都属于前端。文章适合计算机小白，大佬请绕行！
阅读更多2024-11-15
群控系统服务端开发模式-应用开发-前端角色功能开发
群控系统服务端开发模式-应用开发-前端角色功能开发
阅读更多2024-11-15
自定义反序列化过程
需求：student对象中name属性，序列化时将该属性映射为stuname，反序列化时将 Json中的NAME键值对映射到name属性中。
阅读更多2024-11-15
界面控件DevExpress WPF中文教程：TreeList视图及创建分配视图
本文主要介绍DevExpress WPF数据网格组件的TreeList视图及如何创建和分配视图教程，欢迎下载最新版组件体验！
阅读更多2024-11-15
微波无源器件 OMT1 一种用于倍频程接收机前端的十字转门四脊正交模耦合器(24-51GHz)
我们报道了一种用于天文学射电望远镜的毫米波波长接收机的一种十字转门四脊OMT的设计，制造和实测结果。此四脊OMT被直接兼容到一个四脊馈电喇叭来实现可以拓展矩形波导单模带宽的双极化低噪声接收机。使用了2
阅读更多2024-11-15
实战：深入探讨 MySQL 和 SQL Server 全文索引的使用及其弊端
MySQL 中的全文索引自 5.6 版本开始支持InnoDB引擎（在此之前，仅支持MyISAM引擎）。全文索引主要适用于CHARVARCHAR和TEXT类型字段，并提供了的查询方式，可以选择不同的查询
阅读更多2024-11-15
前端 - 使用uniapp+vue搭建前端项目（app端）
前端 - 使用uniapp+vue搭建前端项目（app端）
阅读更多2024-11-15
NFS存储基础操作
NFS 挂载主机在网络断开后卡住通常是由于默认的 NFS 挂载选项导致的。为了避免这种情况，可以使用特定的挂载选项来确保在 NFS 服务器不可用时主机不会卡住。在windows 启用和关闭Window
阅读更多2024-11-15
SpringCloud OpenFeign负载均衡远程调用跨服务调用连接池优化
Spring Cloud OpenFeign 是 Spring Cloud 的一部分，提供了一种声明式的 HTTP 客户端方式来简化服务间的通信。通过 OpenFeign，开发者可以像调用本地方法一样
阅读更多2024-11-15

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

题目列表

2023.04.14

题目

思路

答案

题目

思路

答案

题目

思路

答案

2024.04.19

题目

思路

答案

题目

思路

答案

题目

思路

答案

题目

思路

答案

题目

思路

答案

题目

思路

答案

相关文章