数组相关----二分查找
- Leetcode35：（
二分查找easy） - 《剑指offer》面试题11：（
二分查找） - Leetcode33：（
二分查找medium） - Leetcode81：（
二分查找medium） - 《剑指offer》面试题53(题目一)：（
二分查找） - 《剑指offer》面试题53(题目二)：（
二分查找） - 《剑指offer》面试题53(题目三)：（
二分查找） - Leetcode162：（
二分查找medium） - Leetcode4：（
二分查找hard）
查找插入位置
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5输出: 2
示例 2:
输入: [1,3,5,6], 2输出: 1
示例 3:
输入: [1,3,5,6], 7输出: 4
示例 4:
输入: [1,3,5,6], 0输出: 0
解答
二分查找，注意如果没找到应该返回l：
class Solution {public: int searchInsert(vector & nums, int target) { int l = 0,r = nums.size() - 1; while(l <= r){ int mid = (l + r) >> 1; if(nums[mid] < target) l = mid + 1; else if(nums[mid] > target) r = mid - 1; else return mid; } return l; }}; 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0
解答
class Solution {public: int minNumberInRotateArray(vector rotateArray) { if(rotateArray.size() == 0) return 0; if(rotateArray.size() == 1) return rotateArray[0]; int sz = rotateArray.size(); int l = 0,r = sz - 1; //如果没有旋转，不会进入循环，这样初始化会直接返回最左边元素 int mid = l; while(rotateArray[r] <= rotateArray[l]){ if(r - l == 1){ mid = r; break; } mid = (l + r) >> 1; //如果首尾元素以及中间元素相等，那么没有办法判断中间元素到底是在左半部分还是右半部分，这时只能用顺序查找 if(rotateArray[l] == rotateArray[r] && rotateArray[l] == rotateArray[mid]){ int min = rotateArray[0]; for(int i = 1;i < sz;i++){ if(rotateArray[i] < min) min = rotateArray[i]; } return min; } if(rotateArray[mid] >= rotateArray[l]) l = mid; else if(rotateArray[mid] <= rotateArray[r]) r = mid; } return rotateArray[mid]; }}; 旋转数组中查找数字
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -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
解答
- 首先，如果
nums[mid] == target，那么找到目标元素，返回mid 如果nums[l] < nums[r]，说明l~r范围的元素有序，那么执行正常的二分查找- 否则，根据
mid位置的值判断mid是在左半部分还是右半部分- 如果
nums[mid] ≥ nums[l]，说明mid在左半部分- 当
target > nums[r] && target < nums[mid]，那么target只可能出现在mid的左边，因此在mid左边继续查找 - 否则，
target只可能出现在mid的右边，因此在mid右边继续查找
- 当
- 否则，
mid在右半部分- 当
target > nums[mid] && target < nums[l]，那么target只可能出现在mid的右边，因此在mid右边继续查找 - 否则，
target只可能出现在mid的左边，因此在mid左边继续查找
- 当
- 如果
class Solution {public: int search(vector & nums, int target) { int l = 0,r = nums.size() - 1; while(l <= r){ int mid = (l + r) / 2; if(nums[mid] == target) return mid; if(nums[l] < nums[r]){ if(nums[mid] < target) l = mid + 1; else r = mid - 1; } else{ if(nums[mid] >= nums[l]){//mid在左边 if(target > nums[r] && target < nums[mid]) r = mid - 1; else l = mid + 1; } else{//mid在右边 if(target > nums[mid] && target < nums[l]) l = mid + 1; else r = mid - 1; } } } return -1; }}; 旋转数组中查找数字II
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0输出: true
示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3输出: false
进阶:
- 这是 的延伸题目，本题中的 nums 可能包含重复元素
- 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
解答
相比于前一题，这一题可能包含重复
总的思路还是不变，不过要处理一种特殊情况，即nums[l] == nums[r] && nums[l] == nums[mid]时，此时无法确定mid在左半部分还是右半部分。因此，当出现这种情况时，在区间[l,r]中，执行顺序查找
class Solution {public: bool search(vector & nums, int target) { int l = 0,r = nums.size() - 1; while(l <= r){ int mid = (l + r) / 2; if(nums[mid] == target) return true; if(nums[l] < nums[r]){ if(nums[mid] < target) l = mid + 1; else r = mid - 1; } else{ if(nums[l] == nums[r] && nums[l] == nums[mid]){//无法知道mid在左边还是右边 for(int i = l;i <= r;i++) if(nums[i] == target) return true; return false; } else{ //能确定mid的位置 if(nums[mid] >= nums[l]){//mid在左边 if(target > nums[r] && target < nums[mid]) r = mid - 1; else l = mid + 1; } else{//mid在右边 if(target > nums[mid] && target < nums[l]) l = mid + 1; else r = mid - 1; } } } } return false; }}; 有序数组中查找数字的范围
统计一个数字在排序数组中出现的次数
解答
使用二分查找，分别找到数字的下边界和上边界
class Solution {public: vector searchRange(vector & nums, int target) { int l = searchRangel(nums,target); int r = searchRanger(nums,target); vector v; v.push_back(l); v.push_back(r); return v; } int searchRangel(const vector &nums,int target) { int l = 0,r = nums.size() - 1; int mid; while(l <= r){ mid = (l + r) / 2; if(nums[mid] == target){ if(mid == 0 || nums[mid - 1] != nums[mid]) return mid; else r = mid - 1; } else if(nums[mid] > target) r = mid - 1; else l = mid + 1; } return -1; } int searchRanger(const vector &nums,int target) { int l = 0,r = nums.size() - 1; int mid,end = r; while(l <= r){ mid = (l + r) / 2; if(nums[mid] == target){ if(mid == end || nums[mid + 1] != nums[mid]) return mid; else l = mid + 1; } else if(nums[mid] > target) r = mid - 1; else l = mid + 1; } return -1; }}; 缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字
解答
数组中开始的一些数字与它们的下标相同，如果m不在数组中，则下标m位置的元素是m+1...问题转换为找到数组中下标和元素值不相等的第一个元素
int search(vector nums){ int l = 0, r = nums.size() - 1; int mid = 0; while(l <= r){ mid = (l + r) / 2; if(nums[mid] > mid && nums[mid - 1] == mid - 1) return mid; else if(nums[mid] == mid) l = mid + 1; else r = mid - 1; } return mid;} 数组中数值和下标相等的元素
假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数找出数组中任意一个数值等于其下标的元素。例如，在数组{-3, -1, 1, 3, 5}中，数字3和它的下标相等
解答
int FindSubscript(vector nums){ int l = 0, r = nums.size() - 1; int mid = 0; while(l <= r){ mid = (l + r) / 2; if(nums[mid] == mid) return mid; else if(nums[mid] < mid) r = mid + 1; else l = mid + 1; } return nums[mid];} 查找数组中任一峰值的下标
峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。
示例 1:
输入: nums = [1,2,3,1]输出: 2解释: 3 是峰值元素，你的函数应该返回其索引 2。
示例 2:
输入: nums = [1,2,1,3,5,6,4]输出: 1 或 5 解释: 你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。
说明:
你的解法应该是 O(logN) 时间复杂度的
解答
1）线性查找
遍历数组，对于每个元素，如果该元素的前一元素和后一元素都小于该元素，那么该元素是一个峰值，返回
- 时间复杂度：O(n)
- 空间复杂度：O(1)
2）二分查找
- 如果中间元素比右边的元素小，意味着当前处于一个“升序”中，那么右边(不含当前元素)将会出现一个峰值
- 如果中间元素比右边的元素大，意味着当前处于一个“降序”中，那么左边(包含当前元素)将会出现一个峰值
- 如果中间元素等于右边的元素，那么无法减小区间（所以题目给出了nums[i]不等于nums[i+1]）
使用上述判断一直减小区间，直到区间只有1个元素
- 时间复杂度：O(logn)
- 空间复杂度：O(1)
class Solution {public: int findPeakElement(vector & nums) { int ret = -1; int l = 0,r = nums.size() - 1,mid; while(l < r){ mid = (l + r) >> 1; if(nums[mid] < nums[mid + 1]) l = mid + 1; else if(nums[mid] > nums[mid + 1]) r = mid; //假设输入合法，如果nums[mid] == nums[mid+1]会无限循环 //为了代码的简洁性暂时不处理这种情况 } return l == r ? l : -1; }}; 两个排序数组的中值
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。
请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n))
示例 1:
nums1 = [1, 3]nums2 = [2]中位数是 2.0
示例 2:
nums1 = [1, 2]nums2 = [3, 4]中位数是 (2 + 3)/2 = 2.5
解答
1）归并
使用一个辅助数组，使用归并排序的合并方法将两个数组合并，排成一个按序排序的数组，然后求中值：
class Solution {public: double findMedianSortedArrays(vector & nums1, vector & nums2) { int idx1 = 0,idx2 = 0,idx = 0,sz1 = nums1.size(),sz2 = nums2.size(); vector nums(sz1 + sz2,0); while(idx1 != sz1 && idx2 != sz2){ if(nums1[idx1] < nums2[idx2]) nums[idx++] = nums1[idx1++]; else nums[idx++] = nums2[idx2++]; } while(idx1 != sz1) nums[idx++] = nums1[idx1++]; while(idx2 != sz2) nums[idx++] = nums2[idx2++]; if((sz1 + sz2) % 2 == 0) return (double)(nums[(sz1 + sz2 - 1) / 2] + nums[(sz1 + sz2) / 2]) / 2; else return nums[(sz1 + sz2) / 2]; }}; - 时间复杂度：O(m + n)
- 空间复杂度：O(m + n)
时间复杂度不满足题目要求，但是这种方法也能accept
2）归并（不使用辅助空间）
还是使用归并排序合并的思想，但是不使用辅助数组，根据两个数组的大小判断中值的下标，然后归并过程中递增下标，直到到达中值的下标。这样可以避免使用额外空间
class Solution {public: double findMedianSortedArrays(vector & nums1, vector & nums2) { int idx1 = 0,idx2 = 0,sz1 = nums1.size(),sz2 = nums2.size(); int end1 = (sz1 + sz2 - 1) / 2, end2 = (sz1 + sz2) % 2 ? -1 : (sz1 + sz2) / 2,begin = 0; int num1,num2; while(idx1 != sz1 && idx2 != sz2){ if(begin == end1){ num1 = nums1[idx1] < nums2[idx2] ? nums1[idx1] : nums2[idx2]; if(end2 == -1) return num1; } if(begin == end2){ num2 = nums1[idx1] < nums2[idx2] ? nums1[idx1] : nums2[idx2]; return (double)(num1 + num2) / 2; } if(nums1[idx1] < nums2[idx2]) idx1++; else idx2++; begin++; } while(idx1 != sz1){ if(begin == end1){ num1 = nums1[idx1]; if(end2 == -1) return num1; } if(begin == end2){ num2 = nums1[idx1]; return (double)(num1 + num2) / 2; } idx1++; begin++; } while(idx2 != sz2){ if(begin == end1){ num1 = nums2[idx2]; if(end2 == -1) return num1; } if(begin == end2){ num2 = nums2[idx2]; return (double)(num1 + num2) / 2; } idx2++; begin++; } return 0;//nums1和nums2都为空 }}; - 时间复杂度：O(m + n)
- 空间复杂度：O(1)
时间复杂度不满足题目要求，但是这种方法也能accept
3）二分法
要求O(log(m+n))的时间复杂度，那么必须使用二分法，那么如何进行二分？考虑将数组num1分为2部分[part1,part3]，将数组num2分为2部分[part2,part4]，然后假设part1包含sz1个元素，part2包含sz2个元素。那么我们肯定是要找到part1和part2，使得：
sz1+sz2 = len/2，len为两个数组总长
可以以len/2为长度总和，以part1为基准：
- 当
part1变大时，sz1扩大，那么sz2必须减小，因此part2要减小 - 当
part1变小时，sz1减小，那么sz2必须扩大，因此part2要扩大
现在问题是根据什么标准来扩大或减小part1？这里设4个变量：
part1中最右边的元素（即part1最大的元素）为l1part3中最左边的元素（即part3最小的元素）为r1part2中最右边的元素（即part2最大的元素）为l2part4中最左边的元素（即part4最小的元素）为r2
由于part1和part2必须为数组nums1和nums2组成数组的前半部分，那么必须满足：
l1 <= r1（已经满足）l1 <= r2l2 <= r1l2 <= r2（已经满足）
因此，可以根据中间两个条件是否满足来扩大或减小part1
class Solution {public: double findMedianSortedArrays(vector & nums1, vector & nums2) { if(nums2.size() < nums1.size()) return findMedianSortedArrays(nums2,nums1); int sz = nums1.size() + nums2.size(); int sz1l = 0,sz1r = nums1.size(); int sz1 = 0,sz2 = 0; while(sz1 <= nums1.size()){ sz1 = (sz1l + sz1r) / 2; sz2 = sz / 2 - sz1; int l1 = sz1 == 0 ? INT_MIN : nums1[sz1 - 1]; int r1 = sz1 == nums1.size() ? INT_MAX : nums1[sz1]; int l2 = sz2 == 0 ? INT_MIN : nums2[sz2 - 1]; int r2 = sz2 == nums2.size() ? INT_MAX : nums2[sz2]; if(l1 > r2) sz1r = sz1 - 1; else if(l2 > r1) sz1l = sz1 + 1; else{ if(sz % 2 == 0){ l1 = l1 > l2 ? l1 : l2; r1 = r1 < r2 ? r1 : r2; return (double)(l1 + r1) / 2; } else{ r1 = r1 < r2 ? r1 : r2; return r1; } } } return -1; }}; - 时间复杂度：O(log(min(m,n)))
- 空间复杂度：O(1)