20个外国平面设计网站,苏州哪家做网站好些,江西吉安建设监督网站,定制型网站一般价格目录 一、二分查找简介1.1 朴素二分模板1.2 查找区间左端点模版1.3 查找区间右端点模版 二、leetcode 704.⼆分查找2.1 二分查找2.2 暴力枚举 三、Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置3.1 二分查找3.2 暴力枚举 四、35.搜索插⼊位置4.1 二分查找4.2 暴力枚… 目录 一、二分查找简介1.1 朴素二分模板1.2 查找区间左端点模版1.3 查找区间右端点模版 二、leetcode 704.⼆分查找2.1 二分查找2.2 暴力枚举 三、Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置3.1 二分查找3.2 暴力枚举 四、35.搜索插⼊位置4.1 二分查找4.2 暴力枚举五、69.x的平⽅根4.1 二分查找4.2 暴力枚举 一、二分查找简介
运用场景
当数组是有二段性的时候就可以使用二段性就是指我们可以找到一个相同规律每次都能够选取一个数将当前数组分成两段。我们计算中点的时候有两种计算方法mid (right left) / 2 left (right - left) / 2 和 mid (right left 1) / 2 left (right - left 1)。 这两种方式对于奇数长度的数组来说没区别但是对于偶数长度来说中点有两个点比如长度为四的数组中点就可以是1下标也可以是2下标第一个就是拿到前一个中点第二个就是拿到后一个中点。
1.1 朴素二分模板
模版
while(left right) {int mid left (right - left) / 2;if(……) left mid 1;else if(……) right mid - 1;else return ……;
}1.2 查找区间左端点模版
模版
while(left right) {int mid left (right - left) / 2;if(……) left mid 1;else right mid;
}1.3 查找区间右端点模版
模版
while(left right) {int mid left (right - left 1) / 2;if(……) left mid; else right mid - 1;
}这两个模版详解在目录三的3.1题解中也就是Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置的题解。
细节理解
循环条件left right 这是因为如果当前[left , right ]区间中只有一个元素的时候我们还是需要进行比较。mid left ( right - left) / 2这是因为我们直接使用(left right) / 2来求中间值如果数组很大那么left right的值是可能超过int的范围的减法就没有这种风险。
二、leetcode 704.⼆分查找
题目链接leetcode 704.⼆分查找 题目描述
题目解析
这道题就是在一个有序数组中找到一个等于目标值的元素的下标没找到就返回-1。
2.1 二分查找
解题思路
直接套用上面的朴素模版即可。
解题代码
//时间复杂度O(logN)
//空间复杂度O(1)
class Solution {public int search(int[] nums, int target) {int left 0;int right nums.length-1;while(left right) {int mid left (right-left) / 2;if(nums[mid] target) return mid;else if(nums[mid] target) left mid 1;else right mid - 1;}return -1;}
}2.2 暴力枚举
解题思路
直接遍历数组让目标值与每一个元素相比较如果相等那么就返回当前下标。数组遍历完没找到相等元素返回-1即可。
解题代码
//时间复杂度O(n)
//空间复杂度O(1)
class Solution {public int search(int[] nums, int target) {for(int i 0; i nums.length; i) {if(nums[i] target) return i;}return -1;}
}三、Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置
题目链接Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置 题目描述
题目解析
给的是一个非递减数组意思就是这个数组中元素的值是一定大于或等于前面一个元素的。返回数组中等于target的子数组的头尾下标如果只有一个那么该下标即是头也是尾如果没有返回两个-1。题目要求使用复杂度为O(logN)但是其实O(N^2)和O(N)也能过。
3.1 二分查找
解题思路
当我们要找的是一段区间那么我们可以尝试分别去找左端点和右端点这样就是一个区间了。我们将数组拆分可以以等于target来拆分 分法一一段是 target的元素一段是 target元素这就是求左端点的分法。 分法二一段是 target的元素一段是 target元素这就是求右端点的分法。 上面两种分法都是不断按照同一个规律将数组拆分为两段这就是二段性的体现。求左端点 循环条件left right 因为我们是求的左端点其中并不会写返回语句当我们left和right相等的时候我们如果还进循环就会陷入死循环并且其实这个时候就是我们要求的左端点了。 中点的求法mid left (right - left) / 2; 因为当我们只有两个节点时求取到后一个节点作为中点时就让mid指向right了后续更新mid还会指向这里陷入死循环。 当mid元素 target的时候因为我们求的是左端点当前的左端点肯定在[ left , mid]区间之间并且有可能就是mid所以要让right指向mid。 当mid元素 target 的时候左端点肯定在( mid , right ] 区间所有让 left mid 1 求右端点 循环条件left right 因为我们是求的右端点其中并不会写返回语句当我们left和right相等的时候我们如果还进循环就会陷入死循环并且其实这个时候就是我们要求的右端点了。 中点的求法mid left (right - left 1) / 2; 因为当我们只有两个节点时以第一个节点为中点求取到后面就让mid指向left了后续更新mid还会指向这里又陷入死循环。 当mid元素 target的时候因为我们求的是右端点当前的右端点肯定在[ mid, right ]区间之间并且有可能就是mid所以要让left指向mid。 当mid元素 target 的时候右端点肯定在[ left, mid ) 区间所有让 right mid - 1 在左右端点求取之间我们还要更新一下结果中的端点值如果没找到端点那么就代表给返回[-1, -1]了。边界当数组中没有元素的时候我们去求端点的时候是会直接越界的所以这种情况要单独处理。
解题代码
//时间复杂度O(logN)
//空间复杂度O(1)
class Solution {public int[] searchRange(int[] nums, int target) {int[] ret new int[]{-1,-1};//边界if(nums.length 0) return ret;//查找左端点int left 0;int right nums.length-1;while(left right) {int mid left (right-left)/2;if(nums[mid] target) left mid 1;else right mid;}if(nums[left] target) ret[0] left; else return ret;//查找右端点right nums.length-1;while(left right) {int mid left (right-left1)/2;if(nums[mid] target) right mid -1;else left mid;}ret[1] left;return ret;}
}3.2 暴力枚举
解题思路
我们直接一个for循环遍历数组当遇到等于目标值的时候再一层for循环遍历区间尾即可。
解题代码
//时间复杂度O(n^2)
//空间复杂度O(1)
class Solution {public int[] searchRange(int[] nums, int target) {int[] ret new int[]{-1,-1};for(int i 0; i nums.length; i) {if(nums[i] target) {ret[0] i;for(int j i; j nums.length ;j) {if(j1 nums.length || nums[j1] target) {ret[1] j;return ret;}}}}return ret;}
}优化
我们可以借助滑动窗口的思想当我们遇到等于目标值的元素之后并且left还是初始值的时候我们就可以将ret[ 0 ]更新。每次right遇到等于目标值的元素的时候就更新ret[ 1 ]。
//时间复杂度O(n)
//空间复杂度O(1)
class Solution {public int[] searchRange(int[] nums, int target) {int[] ret new int[]{-1,-1};for(int left -1,right 0; right nums.length; right) {if(nums[right] target) {ret[1] right;if(left -1) {left right;ret[0] right;}}if(nums[right] target) break;}return ret;}
}四、35.搜索插⼊位置
题目链接35.搜索插⼊位置 题目描述
题目解析
数组是升序的当数组中有等于target返回该元素下标。如果没有返回比他小的最近元素的下一个下标。
4.1 二分查找
解题思路
套用上面求左右端点的模版都可以求。有一种边界情况没有求也就是示例3的情况。单独考虑。
解题代码
//时间复杂度O(logN)
//空间复杂度O(1)
class Solution {public int searchInsert(int[] nums, int target) {int left 0;int right nums.length - 1;while(left right) {int mid left (right - left ) / 2;if(nums[mid] target) left mid 1;else right mid;}if(nums[right] target) return right;return right1;}
}class Solution {public int searchInsert(int[] nums, int target) {int left 0;int right nums.length - 1;while(left right) {int mid left (right - left 1) / 2;if(nums[mid] target) right mid - 1;else left mid;}if(nums[right] target) return right;return right1;}
}4.2 暴力枚举
解题思路
直接遍历数组。处理边界情况插入0位置或者插入数组尾。
解题代码
//时间复杂度O(n)
//空间复杂度O(1)
class Solution {public int searchInsert(int[] nums, int target) {for(int i 0; i nums.length; i) {if(nums[i] target) return i;if(nums[i] target i nums.length - 1 nums[i1] target) return i1;} if(nums[0] target) return 0; return nums.length;}
}五、69.x的平⽅根
题目链接69.x的平⽅根 题目描述
题目解析
求一个数的算术平方根向下取整。
4.1 二分查找
解题思路
我们可以将 1 - x 的数分为两个区间小于x算术平方根的区间大于等于算术平方根的区间。因为我们需要求的是小于等于算术平方根的最大值所以相当于求右端点。套用模版处理一下边界情况即可。因为这道题的x范围是整个int所以当我们求平方的时候是可能超出int范围的所以我们使用long。
解题代码
//时间复杂度O(logN)
//空间复杂度O(1)
class Solution {public int mySqrt(int x) {long left 1;long right x;//边界情况if(x 1) return x;while(left right) {long mid left (right - left 1) / 2;if(mid * mid x) left mid;else right mid - 1;}return (int)left;}
}4.2 暴力枚举
解题思路直接使用一个for循环将0 到x 的数遍历看是否符合要求即可。
解题代码
//时间复杂度O(n)
//空间复杂度O(1)
class Solution {public int mySqrt(int x) {for(long i 0; i x; i) {if(i * i x) return (int)i;else if(i * i x (i1) * (i1) x) return (int)i;}return 0;}
}
