企业官网建设流程全解析

北京做网站电话,wordpress 过时,做部门内部使用的网站 用什么开发,ae素材网题目链接#xff1a;LeetCode 34 - Find First and Last Position of Element in Sorted Array。leetcode​ 题目大意#xff1a;给定一个按非递减顺序排序的整数数组 nums#xff0c;和一个目标值 target#xff0c;要求在数组中找到 target 出现的第一个位置和最后一个位…题目链接LeetCode 34 - Find First and Last Position of Element in Sorted Array。leetcode​题目大意给定一个按非递减顺序排序的整数数组 nums和一个目标值 target要求在数组中找到 target 出现的第一个位置和最后一个位置返回 [start, end]。如果不存在返回 [-1, -1]并且算法时间复杂度必须是 O(log⁡n)O(\log n)O(logn)。leetcode​最朴素的想法先找到一个再往两边扫一开始的直觉很自然先用二分查找找到某个 mid使得 nums[mid] target。从 mid 向左扫直到遇到第一个不等于 target 的位置前一个就是 start。从 mid 向右扫直到遇到第一个不等于 target 的位置前一个就是 end。这个思路在正确性上没问题但有一个明显的问题在极端情况下比如 nums [8,8,8,8,8,8]虽然找到一个 8 用了 O(log⁡n)O(\log n)O(logn)但是向左、向右的线性扫描又回到了 O(n)O(n)O(n)。综合起来最坏复杂度是 O(n)O(n)O(n)不满足题目要求的 O(log⁡n)O(\log n)O(logn)。所以向两边线性扫是不行的必须连找左右边界这一步也用二分来做。改进方向用二分专门找边界既然数组有序而且要 O(log⁡n)O(\log n)O(logn)自然想到不仅要用二分找一个 target还要用改造过的二分去分别找最左和最右的 target。这里有两个关键的小问题找左边界时nums[mid] target 时怎么办不能直接返回因为左边可能还有 target。正确做法是记录当前 mid 是一个候选答案然后把 right 收缩到 mid - 1继续往左找。找右边界是不是对称的是的找右边界时nums[mid] target 时记录答案然后把 left 收缩到 mid 1继续往右找。所以思路变成写一个 find_start_position尽量往左压缩找到第一个等于 target 的位置。写一个 find_end_position尽量往右压缩找到最后一个等于 target 的位置。每个函数内部都是一次完整的二分整体只做了常数次二分复杂度是 2⋅log⁡n2 \cdot \log n2⋅logn在大 O 记号下仍然是 O(log⁡n)O(\log n)O(logn)完全符合要求。enjoyalgorithms1​关于2 次二分是不是超了 O(log n)从渐进复杂度的角度2⋅log⁡n2 \cdot \log n2⋅logn、3⋅log⁡n3 \cdot \log n3⋅logn 等都写作 O(log⁡n)O(\log n)O(logn)常数因子会被忽略。enjoyalgorithms​实际上很多官方题解和主流题解就是 “两次边界二分”第一次找左边界第二次找右边界这一点在面试中是完全没有问题的。最终实现两个边界二分函数下面是用 C 写的完整代码拆成三个函数find_start_position找左边界。find_end_position找右边界。searchRange主函数负责处理空数组、调用两个二分并返回结果。代码如下intfind_end_position(int*nums,intnumsSize,inttarget){intleft,right,mid,end_position;left0;rightnumsSize-1;end_position-1;while(leftright){midleft(right-left)/2;if(nums[mid]target){end_positionmid;leftmid1;}elseif(nums[mid]target){leftmid1;}else{// nums[mid] targetrightmid-1;}}returnend_position;}intfind_start_position(int*nums,intnumsSize,inttarget){intleft,right,mid,start_position;left0;rightnumsSize-1;start_position-1;while(leftright){midleft(right-left)/2;if(nums[mid]target){start_positionmid;rightmid-1;}elseif(nums[mid]target){leftmid1;}else{// nums[mid] targetrightmid-1;}}returnstart_position;}/** * Note: The returned array must be malloced, assume caller calls free(). */int*searchRange(int*nums,intnumsSize,inttarget,int*returnSize){intstart_position,end_position;int*result;result(int*)malloc(2*sizeof(int));if(!nums||!numsSize){result[0]-1;result[1]-1;*returnSize2;returnresult;}start_positionfind_start_position(nums,numsSize,target);end_positionfind_end_position(nums,numsSize,target);result[0]start_position;result[1]end_position;*returnSize2;returnresult;}这份代码在 LeetCode 上可以通过所有用例实际提交记录用例88 / 88 全部通过。运行时间0 ms击败 100% 提交。内存使用9.82 MB。leetcode​小结这道题教会了什么这道题的关键不在会不会写二分而在于能否把找到一个 target提升为找到一段 target 的边界知道 边界二分的典型写法命中 target 时不要停而是继续压缩一端能清楚解释为什么两次二分仍然是 O(log⁡n)O(\log n)O(logn)“通过自己一步步把线性往两边扫的想法改进为左右边界都用二分”是一个很典型的从直觉解到最优解的思考路径。如果想把这个模式记牢可以再去刷几道类似的找第一次 / 最后一次出现位置的题尽量统一成一套找左边界 / 右边界的模板会在面试里非常加分。