13 篇
二分算法专区
题目描述 给定一个整数数组 nums 和一个正整数 threshold，需要选择一个正整数作为除数 d。将数组中的每个元素都除以 d 并向上取整，再把这些结果求和。请你找到所有能让最终和不超过 threshold 的除数中，最小 的那个。 题目保证一定存在合法解。 思路 这是一道二分答案 “花费一个 log 的时间，
题目描述 给你两个整数数组 arr1 ， arr2 和一个整数 d ，请你返回两个数组之间的 距离值 。 「距离值」 定义为符合此距离要求的元素数目：对于元素 arr1[i] ，不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。 思路 返回值规则 Arrays.binarySearc
题目描述 给定一个原本按升序排列、且元素互不相同的数组 nums。数组经过若干次旋转后，顺序可能变成类似 [4,5,6,7,0,1,2] 这样的样子。 现在需要找出并返回数组中的最小元素，并且要求时间复杂度为 O(log n)。哎呀，旋转数组又来啦，这次咱不找某个目标值，而是找那个“断开后重新开始”的最小点～
题目描述 给定一个整数数组 arr，需要支持以下操作： public int query(int left,int right,int value) 返回在区间 [left, right] 中，元素值等于 value 的个数。 同时需要多次查询，要求高效。 示例： arr = [1,3,1,2,3] query(0,
题目描述 给定一个整数数组 candies，其中 candies[i] 表示第 i 堆糖果的数量。你可以把每一堆糖果拆成任意数量的子堆，但不能将两堆重新合并。现在要给 k 个小孩分糖，要求每个小孩分到的糖果数量完全相同，且每个小孩至多拿走一堆。请问每个小孩最多能拿到多少糖果？ 思路 依旧是“二分答案”的典型场景：我们关
题目描述 给定一个spell和potion，长度分别为n和m 有一个success，需要做到咒语和药水的能量强度相乘大于success 请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。 思路 先对potion进行排序，然后使用二分算法 当循环结束时，l
题目描述 给定二维数组 points，其中 points[i] = [x_i, y_i] 表示第 i 个点的坐标；再给定字符串 s，s[i] 表示第 i 个点的标签。若一个以原点为中心、边与坐标轴平行的正方形内不存在标签相同的两点（边上视为在内），则称其为合法正方形。请返回合法正方形内最多可以容纳的点数。正方形的边长允
题目描述 给定一个原本升序排列、且元素互不相同的整数数组 nums。数组在某个未知下标处发生了旋转，例如 [0,1,2,4,5,6,7] 可能变成 [4,5,6,7,0,1,2]。 现在需要在旋转后的数组里查找 target。如果存在，就返回它的下标；如果不存在，就返回 -1。题目要求时间复杂度为 O(log n)，所
题目描述 给定一个按非递减顺序排列的整数数组 nums，以及一个目标值 target。需要找出 target 在数组中第一次出现的位置和最后一次出现的位置。 如果数组中不存在 target，返回 [-1, -1]。题目要求时间复杂度为 O(log n)，所以不能慢慢扫一遍啦，拜托，边界问题当然要交给二分查找嘛～
题目描述 给定一个已经按升序排列的数组 nums 和一个目标值 target，需要在数组中找到 target 的下标。 如果 target 不存在，就返回它按顺序插入时应该在的位置。题目要求时间复杂度必须是 O(log n)，所以不能从头扫到尾啦，拜托，二分查找该出场了嘛～ 嘿嘿，排序数组已经排好队啦，咱只
题目描述 给定两个分别已经升序排好的数组 nums1 和 nums2，长度分别为 m 和 n，要找出这两个数组合在一起之后的中位数。题目对时间复杂度卡得很死，要求 O(log(m+n))，所以"合并再排序"的偷懒解法直接被毙掉啦——只能上二分。 两个数组都是排好序的，可中位数偏偏要"合并视角"才能看到，咱得
题目描述 给定一个 m x n 的整数矩阵 matrix，它满足两个条件： 每一行从左到右按非严格递增顺序排列。 每一行的第一个数都大于上一行的最后一个数。 现在要判断 target 是否存在于矩阵中。如果存在，返回 true；否则返回 false。嘿嘿，这个矩阵看起来是二维的，其实从整体顺序看，就像一条被折成好多
二分算法 当 while (left <= right) 退出时，必然满足： right + 1 == left 所以： right 是最后一个 不满足 条件的下标 left 是第一个 满足 条件的下标 “找第一个 ≥ target” 的场景里，结果应返回 left（即成功区间的起点）。 | 名称
