网站建设考虑事项,可以做交互的网站,做网站提升公司形象,wordpress 提权二分算法#xff1a;
34. 在排序数组中查找元素的第一个和最后一个位置给你一个按照非递减顺序排列的整数数组 nums#xff0c;和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target#xff0c;返回 [-1, -1]。你必须设计…二分算法
34. 在排序数组中查找元素的第一个和最后一个位置给你一个按照非递减顺序排列的整数数组 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]class Solution {
public:vectorint searchRange(vectorint nums, int target) {int start searlower(nums, target);int end searupper(nums, target);if(start nums.size() || nums[start] ! target || end -1){return {-1, -1};}return {start, end};}int searlower(vectorint nums, int target){int left 0, right nums.size()-1;while(left right){int mid left (right - left) / 2;//循环不变量://未确定区间为[left, right]//nums[left - 1] target//nums[right 1] targetif(nums[mid] target){left mid 1;}else{right mid - 1;}}return left;}int searupper(vectorint nums, int target){int left 0, right nums.size()-1;while(left right){int mid left (right - left) / 2;//循环不变量://未确定区间为[left, right]//nums[left - 1] target//nums[right 1] targetif(nums[mid] target){left mid 1;}else{right mid - 1;}}return right;}
};定长滑动窗口
//假设滑动窗口固定长度为 n 则代码模板如下
class Solution {
public:int SlideWindow(vectorint nums, int k) {int length nums.size();//在进入循环之前必须先初始化好窗口为最左侧位置的情况//并且维护好这种情况下的相关变量//这里要首先判断一下初始化的结果是否满足题意然后下面的第一次循环就不必//遍历第一种情况了这么做是也是为了满足循环不变量[i - n, i)//循环不变量滑动窗口[i - n, i),窗口长度固定为 nfor (int i n; i length; i) {//此时i位置为窗口本次循环的末位置下标由于是开区间i所以接下来要维护nums[i]的状态//而i-n位置为上一次循环的首位下标我们通常也需要关注维护它的状态使窗口左边界向右移动一位//以上操作进行完毕之后此时窗口区间就变为闭区间[i - n 1, i]了长度还是n//下一次循环之前i区间再次变为半开半闭状态-[i - n, i)}return ...;}
};
不定长滑动窗口
//不定长滑动窗口伪代码
class Solution {
public:int SlideWindow(string s) {// 同方向移动起始的时候都位于 0表示我们定义搜索区间为 [left, right) 此时区间为空区间int left 0;int right 0;while(right Slen){//每一次循环的开始都一定不满足条件//因为上一次循环是从满足条件跳出while的// 这里对状态做修改好让程序在后面检测到满足条件while(满足条件){ // 对状态做修改好让程序在后面检测到不满足条件left; //右移left}//记录当前最接近结果的值right; //右移right}return maxlen;}
};
