济宁哪里有做网站的,域名在哪里申请,国外打开网站会不会乱码,淄博网站搜索排名首先还是说一下通用框架#xff0c;二分的整体结构基本都是设定搜索范围边界#xff0c;检查中心元素#xff0c;根据检查结果移动上界或下界来缩小搜索范围#xff0c;直到范围中只剩一个可选元素#xff08;或没有可选#xff09;。
【搜索插入位置】
给定一个排序数…首先还是说一下通用框架二分的整体结构基本都是设定搜索范围边界检查中心元素根据检查结果移动上界或下界来缩小搜索范围直到范围中只剩一个可选元素或没有可选。
【搜索插入位置】
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
思路
显然初始的上下界是数组本身的起始和结尾。
循环条件我平时习惯设置为lr但本题有可能出现搜索范围内没有target的情况所以我们设置为lr在搜索范围中只剩一个元素的时候多进行最后一次检查来确认究竟这个最后剩下的元素是不是我们想找的target。
class Solution {
public:int searchInsert(vectorint nums, int target) {int l 0, r nums.size() - 1;int mid;while (l r) {mid (l r) / 2;if (nums[mid] target)return mid;else if (nums[mid] target)l mid 1;elser mid-1;}return l;}
};
【搜索二维矩阵】
给你一个满足下述两条属性的 m x n 整数矩阵
每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。
给你一个整数 target 如果 target 在矩阵中返回 true 否则返回 false 。
思路
经典框架下有两种选择一种把矩阵的每一行收尾相接看作一整个数组然后对这个数组进行二分查找就多了一个数组下标到矩阵行列号的转换步骤另一种先在矩阵的第一列二分查找确定该元素如果存在的话应该在哪一行然后再在该行进行常规的二分查找即可。
非经典框架下还有一种思路在该矩阵中某元素向下走一定遇到比自己更大的元素向左走一定遇到比自己更小的元素。因此我们从右上角元素开始依次和target比较根据比较结果来决定本次向下走或向左走直到遇见target查找成功或走出边界查找失败
class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {int l 0, r matrix.size()-1, mid;while (l r) {mid (l r) / 2;if (matrix[mid][0] target)return true;else if (matrix[mid][0] target)l mid 1;elser mid - 1;}if (l 0)return false;int row l - 1;l 0;r matrix[0].size()-1;while (l r) {mid (l r) / 2;if (matrix[row][mid] target)return true;else if (matrix[row][mid] target)l mid 1;elser mid - 1;}return false;}
};
【找第一个和最后一个】
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
思路
分两轮分别查找起始和结束位置只需要在经典框架的基础上修改一些处理的细节第一轮使mid在计算时偏左在mid位置找到target时不是返回而是将右边界移到mid因为左边可能还有target元素要一直缩小范围到左边没有才是找到了起始位置如果起始点查找成功我们开启第二轮第二轮和之前相反使mid在计算时偏右在mid位置找到target时将左边界移到mid。
class Solution {
public:vectorint searchRange(vectorint nums, int target) {vectorint ans(2, -1);if(nums.size()0)return ans;//找左边界int l 0, r nums.size() - 1, mid;while (l r) {mid (l r) / 2;if (nums[mid] target)l mid 1;elser mid;}if (nums[l] target) {//找到左边界的话再找右边界ans[0] l;r nums.size() - 1;while (l r) {mid (l r 1) / 2;if (nums[mid] target)l mid;elser mid - 1;}ans[1] l;}return ans;}
};
【搜索旋转排序数组】
整数数组 nums 按升序排列数组中的值 互不相同 。
在传递给函数之前nums 在预先未知的某个下标 k0 k nums.length上进行了 旋转使数组变为 [nums[k], nums[k1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]下标 从 0 开始 计数。例如 [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target 如果 nums 中存在这个目标值 target 则返回它的下标否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
思路
一种思路是先把旋转的位置找到并将数组分成各自有序的两段然后直接判断目标会在哪一段并在那一段上进行常规的二分查找。
还有一种思路是每次mid都会将数组分成两段其中至少有一段是完全有序的通过这一段的起始和末尾我们可以判断目标是否在这一段中然后根据结果调整范围。
class Solution {
public:int search(vectorint nums, int target) {int l 0, r nums.size() - 1;int mid;while (l r) {mid (l r) / 2;if (nums[mid] nums.back())r mid;elsel mid 1;}int cut l;if (cut 0) {l 0;r nums.size() - 1;} else if (target nums[0]) {l 0;r cut - 1;} else {l cut;r nums.size() - 1;}while (l r) {mid (l r) / 2;if (nums[mid] target)return mid;if (nums[mid] target)r mid - 1;elsel mid 1;}return -1;}
};
【旋转数组最小值】
已知一个长度为 n 的数组预先按照升序排列经由 1 到 n 次 旋转 后得到输入数组。例如原数组 nums [0,1,2,4,5,6,7] 在变化后可能得到
若旋转 4 次则可以得到 [4,5,6,7,0,1,2]若旋转 7 次则可以得到 [0,1,2,4,5,6,7]
注意数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums 它原来是一个升序排列的数组并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
思路
上一题的思路一的第一步...不写了。
class Solution {
public:int findMin(vectorint nums) {int l 0, r nums.size() - 1;int mid;while (l r) {mid (l r) / 2;if (nums[mid] nums.back())r mid;elsel mid 1;}return nums[l];}
};
【两个正序数组的中位数】
给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (mn)) 。
思路
一言难尽的题目作为hard它写起来确实挺费劲但主要是费在不停的折腾那些下标和边界情况的处理细节上了实际上算法本身还挺简单的。
中位数本质上是找下标为size/2的数或者说第size/21大的数偶数的话下标为size/2和下标为size/21取平均所以本题要完成的任务其实就是给定一个k在两个数组中找到整体第k大的数。
假设我们在两个数组中都找到了第k/2位的数记为n1和n2且n1n2。此时n1最大有可能的位次是多少呢
由于数组升序数组1中n1前面的元素肯定都小于n1也就是k/2-1个数。
而数组2中n2及以后的元素肯定都大于n1n2前面的数可能小于n1也可能大于n1最好的情况是全都小于n1此时也有k/2-1个数。
所以最好的情况是比n1小的数有k-2个此时n1的位次是k-1这就意味着n1不可能是我们想找的第k大的数当然数组1中n1前面的数只会更小就更不可能是我们要找的数了于是我们把数组1中n1及以前的元素全部丢弃起始位置来到n1的下一个元素。
由于我们丢了一部分元素在剩下的部分中我们要找的元素就不再排第k位了而是要减掉丢弃部分的大小。
直到k减小到1时也就是我们想找所有剩余元素中的最小的那个此时返回两个数组各自的剩余部分起始元素中较小的那一个就可以了。
然后再来处理一下边界问题由于两个数组长度不一定相同是有可能出现一个数组被全丢完了的情况的此时我们只需要直接返回另一个数组剩余部分中第k大的数就好k是实时的当前要找的位次
class Solution {
public:int findKth(int targetIndex, vectorint nums1, vectorint nums2) {int start1 0, start2 0;int m nums1.size();int n nums2.size();//找到该位序的数while (1) {int step targetIndex / 2;if (start1 m) {return nums2[start2 targetIndex - 1];}if (start2 n) {return nums1[start1 targetIndex - 1];}//要找最小的if (targetIndex 1) {return min(nums1[start1], nums2[start2]);}//找到当前要对比的数字//目前两组都没超int end1 min(m - 1, start1 step - 1);int end2 min(n - 1, start2 step - 1);// 1组丢if (nums1[end1] nums2[end2]) {targetIndex - end1 - start1 1;start1 end1 1;// 2组丢} else {targetIndex - end2 - start2 1;start2 end2 1;}}}double findMedianSortedArrays(vectorint nums1, vectorint nums2) {int m nums1.size(), n nums2.size();if (m n 1)return m 0 ? nums2[0] : nums1[0];if ((m n) % 2 1)return findKth((m n) / 2 1, nums1, nums2);elsereturn (findKth((m n) / 2, nums1, nums2) findKth((m n) / 2 1, nums1, nums2)) /2.0;}
};
