株洲网站制作公司有哪些,用dede做网站后台,域名推荐网站,温州网站建设温州顾得泉#xff1a;个人主页
个人专栏#xff1a;《Linux操作系统》 《C/C》 《LeedCode刷题》
键盘敲烂#xff0c;年薪百万#xff01; 一、二分查找
题目链接#xff1a;二分查找
题目描述 给定一个 n 个元素有序的#xff08;升序#xff09;整型数组 nums 和一…
顾得泉个人主页
个人专栏《Linux操作系统》 《C/C》 《LeedCode刷题》
键盘敲烂年薪百万 一、二分查找
题目链接二分查找
题目描述 给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。示例 1:
输入: nums [-1,0,3,5,9,12], target 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
示例 2:
输入: nums [-1,0,3,5,9,12], target 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示
你可以假设 nums 中的所有元素是不重复的。n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间。
解法
a.定义leftright指针分别指向数组的左右区间。
b.找到待查找区间的中间点mid找到之后分三种情况讨论: i. arr[mid] target说明正好找到返回mid的值; ii. arr[mid] target说明[midright]这段区间都是大于target的因此舍去右边区间在左边[left mid -1]的区间继续查找即让right mid -1然后重复2过程; iii. arr[mid] target说明[leftmid]这段区间的值都是小于target的因此舍去左边区间在右边[mid 1right]区间继续查找即让left mid 1然后重复2过程;
c. 当left与right错开时说明整个区间都没有这个数返回-1
代码实现
int search(int* nums, int numsSize, int target)
{int left 0, right numsSize - 1;while (left right){int mid left (right - left) / 2;if (nums[mid] target) return mid;else if (nums[mid] target)right mid - 1;else left mid 1;}return -1;
} 二、在排序数组中查找元素的第一个和最后一个位置
题目链接在排序数组中查找元素的第一个和最后一个位置
题目描述 给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target返回 [-1, -1]。 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1
输入nums [5,7,7,8,8,10], target 8
输出[3,4]
示例 2
输入nums [5,7,7,8,8,10], target 6
输出[-1,-1]
示例 3
输入nums [], target 0
输出[-1,-1]提示
0 nums.length 105-109 nums[i] 109nums 是一个非递减数组-109 target 109
解法
算法思路: 用的还是二分思想就是根据数据的性质在某种判断条件下将区间一分为二然后舍去其中一个区间然后再另一个区间内查找 方便叙述用×表示该元素resLeft表示左边界resRight表示右边界。
寻找左边界思路: 寻找左边界: 我们注意到以左边界划分的两个区间的特点: ·左边区间[left, resLeft - 1]都是小于×的; ·右边区间(包括左边界)[resLeftright]都是大于等于x的;因此关于mid的落点我们可以分为下面两种情况: 当我们的mid落在[leftresLeft - 1]区间的时候也就是arr[mid]target。说明[left mid]都是可以舍去的此时更新left到mid 1的位置,继续在[mid 1, right]上寻找左边界; 当mid落在[resLeftright]的区间的时候也就是arr[mid] targeto说明[mid 1right](因为mid可能是最终结果不能舍去是可以舍去的此时更新right到mid的位置继续在[leftmid]上寻找左边界; 由此就可以通过二分来快速寻找左边界;
注意:
这里找中间元素需要向下取整。因为后续移动左右指针的时候: ·左指针:left mid 1是会向后移动的因此区间是会缩小的; ·右指针: right mid 可能会原地踏步比如:如果向上取整的话如果剩下1,2两个元素left 1right 2mid 2。更新区间之后leftrightmid 的值没有改变就会陷入死循环)。 因此一定要注意当right mid的时候要向下取整。
寻找右边界思路: 寻右左边界: 用resRight表示右边界;。我们注意到右边界的特点: 左边区间 (包括右边界)[leftresRight]都是小于等于的;右边区间[resRight 1right]都是大于)的; 因此关于mid的落点我们可以分为下面两种情况: 当我们的mid落在[left resRight了区间的时候说明[leftmid - 1]( mid不可以舍去因为有可能是最终结果都是可以舍去的此时更新left到mid的位置。 当mid 落在[resRghet ti, right]的区间的时候说明[midright]内的元素是可以舍去的此时更新ight到mid - 1的位置; 由此就可以通过二分来快速寻找右边界
注意: 这里找中间元素需要向上取整。因为后续移动左右指针的时候: ·左指针: left mid可能会原地踏步(比如:如果向下取整的话如果剩下1,2两个元 素left 1 right 2, mid 1。更新区间之后leftright mid的值没有改变就会陷入死循环)。 ·右指针: right mid - 1是会向前移动的因此区间是会缩小的;因此一定要注意当right mid的时候要向下取整。
二分查找算法总结: 请大家一定不要觉得背下模板就能解决所有二分问题。二分问题最重要的就是要分析题意然后确定要搜索的区间根据分析问题来写出二分查找算法的代码。 要分析题意确定搜索区间不要死记模板不要看左闭右开什么乱七八糟的题解要分析意确定搜索区间不要死记模板不要看左闭右开什么乱七八糟的题解要分析题意确定搜索区间不要死记模板不要看左闭右开什么乱七八糟的题解重要的事情说三遍。
模板记忆技巧: 1.关于什么时候用三段式还是二段式中的某一个一定不要强行去用而是通过具体的问题分析情况根据查找区间的变化确定指针的转移过程从而选择一个模板。 2.当选择两段式的模板时:在求mid的时候只有right - 1的情况下才会向上取整(也就是i取中间数)
代码实现
class Solution
{
public:vectorint searchRange(vectorint nums, int target) {if(nums.size() 0) return {-1, -1}; int begin 0;int left 0, right nums.size() - 1;while(left right){int mid left (right - left) / 2;if(nums[mid] target) left mid 1;else right mid;}if(nums[left] ! target) return {-1, -1};else begin left; left 0, right nums.size() - 1;while(left right){int mid left (right - left 1) / 2;if(nums[mid] target) left mid;else right mid - 1;}return {begin, right};}
}; 三、搜索插入位置
题目链接搜索插入位置
题目描述 给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。
示例 1:
输入: nums [1,3,5,6], target 5
输出: 2示例 2:
输入: nums [1,3,5,6], target 2
输出: 1示例 3:
输入: nums [1,3,5,6], target 7
输出: 4提示:
1 nums.length 104-104 nums[i] 104nums 为 无重复元素 的 升序 排列数组-104 target 104
解法
算法思路:
a.分析插入位置左右两侧区间上元素的特点: 设插入位置的坐标为index根据插入位置的特点可以知道: [leftindex - 1]内的所有元素均是小于target的;[indexright]内的所有元素均是大于等于target的。
b.设left为本轮查询的左边界right为本轮查询的右边界。 根据mid位置元素的信息分析下一轮查询的区间: ·当nums [mid] target时说明mid落在了[indexright]区间上mid左边包括mid本身可能是最终结果所以我们接下来查找的区间在[left,mid]上。因此更新right到mid位置,继续查找。 ·当nums [mid] target时说明mid落在了[leftinde- 1]区间上mid右边但不包括mid本身可能是最终结果所以我们接下来查找的区间在[mid 1 right]上。因此更新left到mid 1的位置继续查找。
c.直到我们的查找区间的长度变为1也就是(left right的时候left或者right所在的位置就是我们要找的结果。
代码实现
class Solution
{
public:int searchInsert(vectorint nums, int target) {int left 0, right nums.size() - 1;while(left right){int mid left (right - left) / 2;if(nums[mid] target) left mid 1;else right mid;}if(nums[left] target) return right 1;return right;}
}; 结语今日的刷题分享到这里就结束了希望本篇文章的分享会对大家的学习带来些许帮助如果大家有什么问题欢迎大家在评论区留言~~~
