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(即成功区间的起点)。 | 名称