网站免费推广策划方案,wordpress在哪里修改密码,中山seo扣费,南阳网站营销外包目录二分法细节1、leetcode 34 在排序数组中查找元素的第一个和最后一个位置2、不完全有序下的二分查找(leetcode33. 搜索旋转排序数组)3、含重复元素的不完全有序下的二分查找(81. 搜索旋转排序数组 II)3、不完全有序下的找最小元素(153. 寻找旋转排序数组中的最小值)4、二维矩… 目录二分法细节1、leetcode 34 在排序数组中查找元素的第一个和最后一个位置2、不完全有序下的二分查找(leetcode33. 搜索旋转排序数组)3、含重复元素的不完全有序下的二分查找(81. 搜索旋转排序数组 II)3、不完全有序下的找最小元素(153. 寻找旋转排序数组中的最小值)4、二维矩阵二分(74. 搜索二维矩阵) 二分法细节
1、计算mid时不能使用(left right)/2,否则有可能计算溢出。 可以使用下面方法计算
mid left ((right - left) 1)2、while(left right)注意符号为 如果是 left right则当我们执行到最后一步left与right重叠时则会跳出循环。但是事实是此时的left和right指向的可能就是我们的目标元素。 3、 left mid 1,right mid - 1; 如果设置left mid right mid,left1,right 8mid 7会陷入死循环mid一直为7. 1、leetcode 34 在排序数组中查找元素的第一个和最后一个位置
https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/ 在普通的二分上加上检索区间的左右边界需要注意特殊的输入情况。
class Solution {
public:vectorint searchRange(vectorint nums, int target) {if(nums.empty()) return{-1,-1};int left 0;int right nums.size() - 1;while(left right){int mid left ((right - left) 1);if(nums[mid] target){int l mid;int r mid;//寻找左边界//寻找右边界while( l 0 nums[l] target) l--;while(r nums.size() - 1 nums[r] target) r;l 1;r - 1;if(l 0) l 0;if(r nums.size() - 1) r nums.size() - 1;return {l,r};}else if(nums[mid] target){right mid -1;}else{left mid 1;}}return {-1,-1};}
};2、不完全有序下的二分查找(leetcode33. 搜索旋转排序数组)
https://leetcode-cn.com/problems/search-in-rotated-sorted-array/ 升序排列的整数数组 nums 在预先未知的某个点上进行了旋转例如 [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] 。
请你在数组中搜索 target 如果数组中存在这个目标值则返回它的索引否则返回 -1 。 注意这里的数组中不包含重复的元素。 示例 1 输入nums [4,5,6,7,0,1,2], target 0 输出4 示例 2 输入nums [4,5,6,7,0,1,2], target 3 输出-1 示例 3 输入nums [1], target 0 输出-1 之前使用的二分都是在数组是有序的背景下如果不完全有序时也是可以使用二分查找的。 已知分开来的两个子数组都是有序递增的。那么如果nums[mid] nums[left]则说明mid和left一定落在同一个子数组里反之nums[mid] nums[left],说明mid和left不在同一个子数组里并且此时可以肯定left在数组1mid在数组2。 注意这里的mid还是通过left和right的下标来求得的也就是说mid还是在left与right之间。 如果mid和left在同一个子数组中那么target一共有2种分布的可能 1、target在mid左边此时有target nums[left] target nums[mid],令right mid - 1这样就在有序的数组1中进行寻找了 2、target在mid右边此时有 target nums[mid] || target nums[left],令left mid 1,缓慢地将left和right指针驱赶到同一个有序区间内。 如果mid和right在同一个子数组中那么target一共有2种分布的可能 1、target nums[right] target nums[mid] 此时查找部分就落在右半部分令left mid 1这样就在有序的数组2中进行寻找了 2、target nums[right] || target nums[mid] 此时mid落在左半部分应该令right mid - 1,将两个指针驱赶到同一个有序区间内 AC代码
class Solution {
public:int search(vectorint nums, int target) {int left 0;int right nums.size() - 1;while(left right){int mid left ((right - left) 1);if(nums[mid] target){return mid;}//left and mid 落在同一个数组if(nums[mid] nums[left]){//mid和left一个数组,target在左边数组if(target nums[left] target nums[mid]){right mid - 1;}//mid和right一个数组else if(target nums[mid] || target nums[left]){left mid 1;}}//left and mid 落在不同数组else if(nums[mid] nums[left]){//target在mid 和 right之间if(nums[mid] target target nums[right]){left mid 1;}//target在left 和mid之间else if(target nums[right] || target nums[mid]){right mid - 1;}}}//没有查找到return -1;}
};这一题思路还是比较麻烦的不易想到还需要加深理解才行。
3、含重复元素的不完全有序下的二分查找(81. 搜索旋转排序数组 II)
https://leetcode-cn.com/problems/search-in-rotated-sorted-array-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[left] nums[mid]时这里可能会有问题。 这时我们需要让left即可。注意在书写代码的时候我们需要在left后这次循环就结束所以我们把nums[left] nums[mid]的情况放到最后处理即可
class Solution {
public:int search(vectorint nums, int target) {int left 0;int right nums.size() - 1;while(left right){int mid left ((right - left) 1);if(nums[mid] target){return true;}//left and mid 落在同一个数组if(nums[mid] nums[left]){//mid和left一个数组,target在左边数组if(target nums[left] target nums[mid]){right mid - 1;}//mid和right一个数组else if(target nums[mid] || target nums[left]){left mid 1;}}//left and mid 落在不同数组else if(nums[mid] nums[left]){//target在mid 和 right之间if(nums[mid] target target nums[right]){left mid 1;}//target在left 和mid之间else if(target nums[right] || target nums[mid]){right mid - 1;}}elseleft;}//没有查找到return false;}
};3、不完全有序下的找最小元素(153. 寻找旋转排序数组中的最小值)
https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/ 假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。
请找出其中最小的元素。 示例 1 输入nums [3,4,5,1,2] 输出1 示例 2 输入nums [4,5,6,7,0,1,2] 输出0 示例 3 输入nums [1] 输出1 由于跳变点小于左边的值大于右边的值。所以当nums[mid] nums[left]时说明跳变点在mid与left之间因为mid与right之间必然是递增的跳变只有一次。 当nums[mid] nums[left]说明mid与left之间是单调递增的。 当nums[mid] nums[left]说明此时mid与left重合了,此时需要将left向右移动1格然后重新迭代。 class Solution {
public:int findMin(vectorint nums) {if(nums.size() 1) return nums[0];int left 0;int right nums.size() - 1;while(left right){if(nums[left] nums[right]) return nums[left];int mid left ((right - left) 1);if(nums[mid] nums[left]) right mid;else if(nums[mid] nums[left]) left mid 1;else if(left mid) left;}return -1;}
};4、二维矩阵二分(74. 搜索二维矩阵)
https://leetcode-cn.com/problems/search-a-2d-matrix/ 编写一个高效的算法来判断 m x n 矩阵中是否存在一个目标值。该矩阵具有如下特性
每行中的整数从左到右按升序排列。 每行的第一个整数大于前一行的最后一个整数。 示例 1 输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target 3 输出true 示例 2 输入matrix [[1,3,5,7],[10,11,16,20],[23,30,34,50]], target 13 输出false 示例 3 输入matrix [], target 0 输出false 只要将二维数组展开成一维数组即可用普通的二分。 需要注意的是将mid转换成行列坐标; mid/col 得到的是行数 mid % col 得到的是列数 class Solution {
public:bool searchMatrix(vectorvectorint matrix, int target) {//获得行数int row matrix.size();if(row 0) return false;//获得列数int col matrix[0].size();int left 0;int right row * col - 1;while(left right){int mid left ((right - left) 1);if(target matrix[mid/col][mid%col]) return true;else if(target matrix[mid/col][mid%col]) left mid 1;else right mid - 1;}return false;}
};
