剑指offer68-77二分查找、排序
二分查找系列
剑指 Offer II 068. 查找插入位置
给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
输入: nums = [1,3,5,6], target = 5
输出: 2
找目标的下标，找不到输出应该插入的下标
mid = left + ((right - left) >> 1) 的写法比 mid = (left + right) / 2 好，因为 left + right 可能会溢出，同时位运算的效率更高； >> 1 作用相当于除二，这个看leetcode汇总
当出现 nums[mid] >= target 的情况，还需要加一个判断 mid == 0 || nums[mid - 1] < target，若成立则说明，前一个数比 target 小，那么就找到了位置。若在 while 循环内都未找到符合要求的位置，那么说明 target 比所有的数都要大，需要插入到数组的最后一个数字之后，即返回 nums.size()。
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] >= target) {
if (mid == 0 || nums[mid - 1] < target) {
return mid;
}
right = mid - 1;
}
else {
left = mid + 1;
}
}
return nums.size();
}
};
剑指 Offer II 069. 山峰数组的顶部
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 = [3,4,5,1]
输出：2
左右都比它小，位置>0，题目保证是山峰数组，这里只需要返回在数组里的位置
方法二分查找
使用二分查找时，题目中已经明确山峰不在数组的首尾，所以可以把 left 和 right 初始化为 1 和 arr.size() - 2。
代码
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 1;
int right = arr.size() - 2;
while (left <= right) {
int mid = left + ((right - left) >> 1);//mid = (left + right) / 2
if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
return mid;
}
arr[mid] > arr[mid - 1] ? left = mid + 1 : right = mid - 1;
}
return -1;
}
};
剑指 Offer II 070. 排序数组中只出现一次的数字
给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2
如果是要求O（n）的话，可以直接异或，因为最后只剩0和一个单独的数异或，比如000异或100=100
方法一：根据对不相等进行二分查找
下面保留疑问，如果不相等，为什么能直接让right=mid-1，万一在mid和i之间呢，本身是与i做的比较，应该让right=i-1才对吧，但是这样通不过，原先那样可以通过
代码
原先的代码可以通过
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int left = 0;
int right = nums.size() / 2 - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
int i = 2 * mid;
if (nums[i] != nums[i + 1]) {
if (i == 0 || nums[i - 1] == nums[i - 2]) {
return nums[i];
}
right = mid - 1;
}
else {
left = mid + 1;
}
}
return nums.back();
}
};
方法二：也根据成对进行二分查找
对于目标x，因为前面都是成对的，因此mid如果是偶数就应该和前面相比较，如果mid是奇数就应该和后面作比较，但是由于数组是从0开的的，因此正好反过来 应该mid是偶数就应该和前面作比较，是奇数就应该和前面作比较。在指针移动时，如果相等还好说明在后面，就应该left=mid+1，但如果不等于，就可能当前元素就是，那么right就应该=mid而不是mid-1
在判断mid是否是奇偶时，由于
因此不用判断奇偶了，直接比较
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left+ (right - left)>1 ;
if (nums[mid] == nums[mid ^ 1]) {
left = mid + 1;
}
else {
right = mid;
}
}
return nums[left];
}
};
方法三 偶数下标的二分查找
成对出现且数组从0开始，因此目标下标一定是偶数，那么目标左侧的偶数下标与其右边一定都是相等的，目标右侧的偶数下标和其右侧一定是不同的。
因此只看偶数就可以了，在求mid时，如果是偶数，那就是当前值，如果是奇数需要-1，但是有个特点
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int low = 0, high = nums.size() - 1;
while (low < high) {
int mid = (high - low) / 2 + low;
mid -= mid & 1;
if (nums[mid] == nums[mid + 1]) {
low = mid + 2;
}
else {
high = mid;
}
}
return nums[low];
}
};
剑指 Offer II 071. 按权重生成随机数
输入：
inputs = [“Solution”,“pickIndex”]
inputs = [[[1]],[]]
输出：
[null,0]
解释：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。
游戏开发中经常会碰到这样的需求：从一系列道具中随机抽出一个发给玩家，由于道具的价值不一样，所以抽取的概率并不是平均的。后台会处理成高价值的东西很难得到，要实现这种效果，需要给每个道具指定一个权重。比如道具A的权重是99，道具B的权重是1，那么99%的概率会抽到道具A，这就是基于权重的随机算法。
A=[3,5,4],W=[1,2,7]
3的权重为1/(1+2+7)=10%
5的权重为2/(1+2+7)=20%
那么100次选中3的次数可能是10次
选中5的概率是20次
本题没有A数组，仅有W数组，也就是看W下标的概率，比如上面的3就变成了下标0的概率是10%
方法：前缀和+二分查找
对于[1,3,5,4,2]的权重，新建一个数组，内容是前面加起来，就如上图一样生成的数组，那么等概率在[1, vector.back()] 生成数，然后再二分查找这个数在vector里的下标
class Solution {
public:
vector<int> acc;
public:
Solution(vector<int>& w) {
acc.resize(w.size(), 0);
int sum = 0;
for (int i = 0; i < w.size(); ++i) {
sum += w[i];
acc[i] = sum;
}
}
int pickIndex() {
int rad = rand() % acc.back() + 1;
int left = 0;
int right = acc.size() - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (rad <= acc[mid]) {
if (mid == 0 || rad > acc[mid - 1]) {
return mid;
}
right = mid - 1;
}
else {
left = mid + 1;
}
}
return -1;
}
};
剑指 Offer II 072. 求平方根
给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。
正数的平方根有两个，只输出其中的正数平方根。
如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。
输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842…，由于小数部分将被舍去，所以返回 2
方法 二分查找找k^2<=x
class Solution {
public:
int mySqrt(int x) {
int l = 0, r = x, ans = -1;
while (l <= r) {
int mid = l + (r - l) / 2;
if ((long long)mid * mid <= x) {
ans = mid;
l = mid + 1;
}
else {
r = mid - 1;
}
}
return ans;
}
};
剑指 Offer II 073. 狒狒吃香蕉
输入：piles = [30,11,23,4,20], h = 6
输出：23
一小时只能减x，如果能减没，一小时内就不动了，如果减不没下一个小时再减，以上面的输入为例，一小时减23个，30需要两次，11一次，23一次，4一次，20一次，所以需要2+1+1+1+1=6次，而这也是h=6需要的
方法 二分查找尝试
一小时最小是1，最大是数组里最大的元素
也就是在[1,max]里最小且能满足在规定时间内吃完
代码
class Solution {
private:
// 返回狒狒速度 k 时需要吃完香蕉的时间[3,6,7,10]
int countTime(vector<int>& piles, int k) {
int t = 0;
for (auto& p : piles) {
// t += (p - 1) / k + 1;
t += p / k;
t += ((p % k) > 0);
}
return t;
}
public:
int minEatingSpeed(vector<int>& piles, int h) {
int left = 1;
int right = *max_element(piles.begin(), piles.end());
while (left <= right) {
int mid = left + ((right - left) >> 1);
if (countTime(piles, mid) <= h) {
if (mid == 1 || countTime(piles, mid - 1) > h) {
return mid;
}
right = mid - 1;
}
else {
left = mid + 1;
}
}
return -1;
}
};
剑指 Offer II 074. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
合并分区，重复的进行合并
代码
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.size() == 0) {
return {};
}
sort(intervals.begin(), intervals.end());
vector<vector<int>> merged;
for (int i = 0; i < intervals.size(); ++i) {
int L = intervals[i][0], R = intervals[i][1];
if (!merged.size() || merged.back()[1] < L) {
merged.push_back({ L, R });
}
else {
merged.back()[1] = max(merged.back()[1], R);
}
}
return merged;
}
};
剑指 Offer II 075. 数组相对排序
给定两个数组，arr1 和 arr2，
arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。
输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]
代码
将arr2放到哈希表里，先出现的元素是小的
然后重新定义比较函数，具体看下面的注解
class Solution {
public:
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
unordered_map<int, int> rank;
for (int i = 0; i < arr2.size(); ++i) {
rank[arr2[i]] = i;
}
sort(arr1.begin(), arr1.end(), [&](int x, int y) {
if (rank.count(x)) {
return rank.count(y) ? rank[x] < rank[y] : true;
/*在哈希表里的会小一点
* 如果一个在哈希表里一个不在哈希表里，那么在哈希表里的大
* 传递了两个元素，第一个元素在哈希表，第二个元素不在哈希表，那么第二个元素大
* 传递两个元素，是想判断这两个哪个大，很显然第二个大，那么就返回true
* 如果两个都在哈希表里，那么比较哈希表键对应的值
* 两个元素，如果第一个大即rank[x] > rank[y]，那么返回false
* 如果第二个大，那么返回true
*/
}
else {
return rank.count(y) ? false : x < y;
/* 如果第一个不在哈希表里，那么看第二个是否在哈希表里
* 如果第二个不在哈希表里，那就是看这两个谁大了
* 如果第二在哈希表里，由于在哈希表里的小，那么就返回false
*/
}
});
return arr1;
}
};
剑指 Offer II 076. 数组中的第 k 大的数字
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
方法一：基于快速排序的选择方法
可以先排序然后再找到第k个大的元素，但如果这样就没有利用上第k个最大元素的条件了。看本题先看快速排序在基本算法整理那里，
与快速排序差不多的是都有两个指针，这个看基本算法整理的快速排序2
如果函数返回的中间值位置刚好为 k - 1，那么数组 k - 1位置的数字就是第 k 大的数字。如果函数返回的位置大于 k - 1，那么第 k 的数字一定在当前中间值的左侧，于是对左侧区间进行分区。反之，则对右侧区间进行分区。
代码
class Solution {
private:
int partition(vector<int>& nums, int start, int end) {
int rad = rand() % (end - start + 1) + start;
swap(nums[rad], nums[end]);
int big = start - 1;
for (int i = start; i < end; ++i) {
if (nums[i] > nums[end]) {
big++;
swap(nums[big], nums[i]);
}
}
big++;
swap(nums[big], nums[end]);
return big;
}
public:
int findKthLargest(vector<int>& nums, int k) {
int start = 0;
int end = nums.size() - 1;
int i = partition(nums, start, end);
while (i != k - 1) {
i < k - 1 ? start = i + 1 : end = i - 1;
i = partition(nums, start, end);
}
return nums[k - 1];
}
};
方法二：最小堆获得前k大
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 0; i < nums.size(); ++i) {
if (i < k) {
heap.push(nums[i]);
}
else if (nums[i] > heap.top()) {
heap.pop();
heap.push(nums[i]);
}
}
return heap.top();
}
};
剑指 Offer II 077. 链表排序
给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
