博客主页：⭐️这是一只小逸白的博客鸭~⭐️ 欢迎 关注❤️点赞收藏⭐️评论 小逸白正在备战实习，经常更新面试题和LeetCode题解，欢迎志同道合的朋友互相交流~ 若有问题请指正，记得关注哦，感谢~
往期文章 ：
LeetCode 剑指 Offer II 链表 专题总结LeetCode 剑指 Offer II 哈希表 专题总结LeetCode 剑指 Offer II 栈 专题总结LeetCode 剑指 Offer II 队列 专题总结LeetCode 剑指 Offer II 树（上） 专题总结LeetCode 剑指 Offer II 树（下） 专题总结LeetCode 剑指 Offer II 堆 专题总结LeetCode 剑指 Offer II 前缀树(上) 专题总结LeetCode 剑指 Offer II 前缀树(下) 专题总结
目录068. 查找插入位置069. 山峰数组的顶部070. 排序数组中只出现一次的数字071. 按权重生成随机数072. 求平方根073. 狒狒吃香蕉
068. 查找插入位置题目：
给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
示例：
输入: nums = [1,3,5,6], target = 5
输出: 2
提示:
1 <= nums.length <= 104-104 <= nums[i] <= 104nums 为无重复元素的升序排列数组-104 <= target <= 104
思路：
要达到O(log n)的复杂度，只能用二分算法
target 插入的位置 ans应该满足 nums[ans - 1] < target <= nums[ans]
套用二分模板，在 target <= nums[ans] 的时候记录ans值
class Solution {
public:
int searchInsert(vector& nums, int target) {
int left = 0, right = nums.size() - 1;
// ans记录位置，初始值为nums.size()是为了防止 target大于数组内所有值
int ans = nums.size();
while(left <= right) {
int mid = ((right - left) >> 1) + left;
// nums[ans - 1] < target <= nums[ans],所以小于等于且ans记录位置
if(target <= nums[mid]) {
ans = mid;
right = mid - 1;
}else {
left = mid + 1;
}
}
return ans;
}
};
069. 山峰数组的顶部
题目：
符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：
arr.length >= 3存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i]arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i ，即山峰顶部。
示例：
输入：arr = [1,3,5,4,2]
输出：2
提示：
3 <= arr.length <= 1040 <= arr[i] <= 106题目数据保证 arr 是一个山脉数组
思路：
二分查找
arr[mid] < arr[mid + 1] 时：表示此时在答案左边
arr[mid] >= arr[mid + 1]时：表示此事在答案右边且可能是答案，用ans记录
class Solution {
public:
int peakIndexInMountainArray(vector& arr) {
int left = 0, right = arr.size() - 1;
int ans = 0;
while(left <= right) {
int mid = ((right - left) >> 1) + left;
// 数组最小长度为3，不用担心越界问题
if(arr[mid] < arr[mid + 1]) {
left = mid + 1;
}else {
// arr[mid] > arr[mid + 1] 时记录
ans = mid;
right = mid - 1;
}
}
return ans;
}
};
070. 排序数组中只出现一次的数字
题目：
给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。
示例：
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
输入: nums = [3,3,7,7,10,11,11]
输出: 10
提示:
1 <= nums.length <= 1050 <= nums[i] <= 105
进阶: 采用的方案可以在 O(log n) 时间复杂度和 O(1) 空间复杂度中运行吗？
思路：
通过观察可以知道答案必然在数组下标为偶数的位置上，而且这个数组是升序的，可以使用二分查找
所以我们在查找时只需考虑偶数位，奇数跳过，知道这个即可用二分实现 O(log n) 复杂度nums[mid] == nums[mid + 1] 代表这个不是答案且两个数一样，都跳过 left = mid + 2;nums[mid] < nums[mid + 1] 代表这个数在答案右边也有可能是答案，ans保存
class Solution {
public:
// 注释的奇数，偶数说的是数组下标
// 思路：答案必定在偶数位上，因为相同的两个数都相邻，所以可以根据数组下标以及相邻数大小判断答案在左边还是在右边
int singleNonDuplicate(vector& nums) {
// 这样就不用担心数组越界问题了
if(nums.size() == 1)
return nums[0];
int left = 0, right = nums.size() - 1;
int ans = 0;
while(left <= right) {
int mid = ((right - left) >> 1) + left;
// 答案一定在数组下标偶数位上，所以只考虑偶数位
if(mid & 1 == 1) mid--;
if(nums[mid] == nums[mid + 1]) {
// 如果这个数不是答案，相当于他右边也不是，直接跳过
left = mid + 2;
}else {
ans = mid;
right = mid - 1;
}
}
return nums[ans];
}
};
071. 按权重生成随机数
题目：
给定一个正整数数组 w ，其中 w[i] 代表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。
例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。
也就是说，选取下标 i 的概率为 w[i] / sum(w) 。
示例：
输入：
inputs = [“Solution”,“pickIndex”,“pickIndex”,“pickIndex”,“pickIndex”,“pickIndex”]
inputs = [[[1,3]],[],[],[],[],[]]
输出：
[null,1,1,1,1,0]
解释：
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。
由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
…
诸若此类。
提示：
1 <= w.length <= 100001 <= w[i] <= 10^5pickIndex 将被调用不超过 10000 次
思路：
前缀和 + 二分查找
以权重数组 [1, 2, 3, 4] 为例，标 0 的概率为 10% ，下标 1 、2 、 3 的概率为 20% 、30% 和40%。先按等概率生成 1 ~ 10，则每个数字的概率的都为 10%。如果生成 1 则选择下标 0，概率为 10%；如果生成 2 或 3 则选择下标 1，概率为 20%；如果生成 4、5 或 6 则选择下标 2，概率为 30%；如果生成 7、8、9 或 10 则选择下标 3，概率为 40%。用前缀和数组pre存储，因为pre递增，所以二分查找pre数组
答案满足：pre[mid - 1] < rand() <= pre[mid] ， （mid == 0）直接返回，防止越界
class Solution {
public:
vector pre;
Solution(vector& w) {
int sum = 0;
for(int i : w) {
sum += i;
pre.push_back(sum);
}
}
int pickIndex() {
int left = 0, right = pre.size() - 1;
// 取随机数
int target = rand() % pre.back() + 1;
while(left <= right) {
int mid = ((right - left) >> 1) + left;
if(target <= pre[mid] ) {
if(mid == 0 || target > pre[mid - 1])
return mid;
right = mid - 1;
}else {
left = mid + 1;
}
}
return -1;
}
};
072. 求平方根
题目：
给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。
正数的平方根有两个，只输出其中的正数平方根。
如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。
示例：
输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842…，由于小数部分将被舍去，所以返回 2
提示:
0 <= x <= 231 - 1
思路：
二分查找
mid * mid <= x，则答案在右边或本身，ans记录
mid * mid > x，则答案在左边
将mid * mid <= x 换成mid <= x / mid防止乘积过大，同时过滤0，防止除数为0
class Solution {
public:
int mySqrt(int x) {
// 防止除数为0
if(x == 0)
return 0;
int left = 1, right = x;
int ans = 0;
while(left <= right) {
int mid = ((right - left) >> 1) + left;
// 将原本的 mid * mid <= x 可能越界，所以换格式
if(mid <= x / mid) {
ans = mid;
left = mid + 1;
}else {
right = mid - 1;
}
}
return ans;
}
};
073. 狒狒吃香蕉
题目：
狒狒喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
狒狒可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉，下一个小时才会开始吃另一堆的香蕉。
狒狒喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
示例：
输入: piles = [3,6,7,11], H = 8
输出: 4
提示：
1 <= piles.length <= 10^4piles.length <= H <= 10^91 <= piles[i] <= 10^9
思路：
速度取值[1, piles.max]，因为速度至少为1，超过数组最大值也只能吃数组最大值那么多
然后对区间二分查找，check(piles, mid)函数计算mid速度所用时间check(piles, mid) <= h 代表此速度能够完成，即右边不用考虑
check(piles, mid - 1) > h 代表速度减一就无法完成，即找到最小速度 check(piles, mid) > h 代表此速度无法完成，左边不用考虑，考虑右边
class Solution {
public:
int minEatingSpeed(vector& piles, int h) {
int left = 1, right = 0;
for(int& i : piles) {
right = max(right, i);
}
// 二分查找[1,piles.max]
while(left <= right) {
int mid = ((right - left) >> 1) + left;
// 如果当前速度已经满足 <= h 内吃完
if(check(piles, mid) <= h) {
// 速度减一不满足 <= h 内吃完，则得到速度最小值
if(mid == 1 || check(piles, mid - 1) > h) {
return mid;
}
// 答案只可能在左边
right = mid - 1;
}else {
// 否则答案在右边
left = mid + 1;
}
}
return -1;
}
// 计算mid速度吃完的时间
int check(vector& piles, int mid) {
int time = 0;
for(int& i : piles) {
time += i / mid;
time += ((i % mid) > 0);
}
return time;
}
};
