企业官网建设流程全解析

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 `nums`，和一个目标值 `target`。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 `target`，返回 `[-1, -1]`。 你必须设计并实现时间复杂度为 `O(log n)` 的算法解决此问题。

关键:循环不变量L-1始终是红色(红色小于target的数)R+1始终是蓝色(蓝色大于target的数)根据循环不变量，R+1是我们要找的答案， 由于循环结束后R+1=L所以答案也可以用L表示 思路： 这篇文章，https://blog.csdn.net/groovy2007/article/details/78309120，里那句“关键不在于区间里的元素具有什么性质，而是区间外面的元素具有什么性质。”之后醍醐灌顶，建立了我自己的二分查找心智模型，和up主的有些类似。 也就是看最终左右指针会停在哪里。 如果我们要找第一个大于等于x的位置，那么我就假设L最终会停在第一个大于等于x的位置，R停在L的左边。 这样按照上面那句话，可以把循环不变式描述为“L的左边恒小于x，R的右边恒大于等于x”，这样一来，其他的各种条件就不言自明了。 根据二分查找改编：1、假设left指向大于等于target的位置， 而right指向小于target的位置2、二叉法有四种情况：大于等于，大于，小于等于，小于3、lower_bound返回的left永远指向大于等于target情况，所以是第一种情况（大于等于）4、大于可以转换成>=(target+1)小于等于可以转换成(>target)的位置的基础上再减1小于可以转换成(>=target)的位置的基础上再减1代码：classSolution{//开始位置是>=，结束位置是<=//假设left指向大于等于target的位置， 而right指向小于target的位置//二叉法有四种情况：大于等于，大于，小于等于，小于//lower_bound返回的left永远指向大于等于target情况publicintlowerBound(int[]nums,inttarget){intleft=0;intright=nums.length-1;// int mid = left + (right-left)/2;while(left<=right){intmid=(left+right)/2;if(nums[mid]<target){left=mid+1;}else{right=mid-1;}}returnleft;}publicint[]searchRange(int[]nums,inttarget){intstart=lowerBound(nums,target);if(start==nums.length||nums[start]!=target){returnnewint[]{-1,-1};}intend=lowerBound(nums,target+1)-1;returnnewint[]{start,end};}}

162. 寻找峰值

峰值元素是指其值严格大于左右相邻值的元素。 给你一个整数数组 `nums`，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 **任何一个峰值** 所在位置即可。 你可以假设 `nums[-1] = nums[n] = -∞` 。 你必须实现时间复杂度为 `O(log n)` 的算法来解决此问题

思路：1、根据红蓝染色法来做，红色表示某一个峰顶左侧，蓝色表示为某一个峰顶右侧2、初始比较nums[mid]与nums[mid+1]关系：ifnums[mid]<nums[mid+1],那么就可以把[0,mid]之间都染成红色，因为这个区间必然在某一个峰顶的左侧。则要确认另外一个区间的颜色。此时移动left。ifnums[mid]>=nums[mid+1],那么就可以把[mid,n-1]之间都染成蓝色，因为这个区间要么是峰顶，要么峰顶左侧。也要确认另外一个区间的颜色。此时移动right。 代码：classSolution{publicintfindPeakElement(int[]nums){//红蓝染色法：红色表示峰顶的左侧，蓝色表示峰顶或者峰顶的右侧intleft=0;// nums[n] = -∞,那么n-1的位置要么是峰顶，要么是峰顶右侧，所以必然是蓝色intright=nums.length-2;while(left<=right){intmid=(left+right)/2;if(nums[mid]<nums[mid+1]){//[0,mid]是红色，在峰顶左边left=mid+1;//要确认[mid+1,n-2]的颜色}else{//[mid,n-2]是蓝色，在峰顶右边right=mid-1;//要确认[0,mid-1]位置}}returnleft;}}

153. 寻找旋转排序数组中的最小值

已知一个长度为 `n` 的数组，预先按照升序排列，经由 `1` 到 `n` 次 **旋转** 后，得到输入数组。例如，原数组 `nums = [0,1,2,4,5,6,7]` 在变化后可能得到： - 若旋转 `4` 次，则可以得到 `[4,5,6,7,0,1,2]` - 若旋转 `7` 次，则可以得到 `[0,1,2,4,5,6,7]` 注意，数组 `[a[0], a[1], a[2], ..., a[n-1]]` **旋转一次** 的结果为数组 `[a[n-1], a[0], a[1], a[2], ..., a[n-2]]` 。 给你一个元素值 **互不相同** 的数组 `nums` ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 **最小元素** 。 你必须设计一个时间复杂度为 `O(log n)` 的算法解决此问题

思路：1、根据红蓝染色法的思路，红色表示最小值的左侧，蓝色表示最小值或者最小值的右侧。2、注意的是比较规则是mid和最后一个数比较，而nums数组要么是一段递增的数组，要么是两段递增的数组，且第一段递增的数组比第二段递增的数组要高。3、ifnums[mid]<nums[n-1],那么nums可以是一段递增的数组，也可以是两段递增的数组ifnums[mid]>nums[n-1],那么nums只能是两段递增的数组。4、数组中最后一个数肯定是蓝色，要么是最小值，要么是最小值的右侧 代码：classSolution{publicintfindMin(int[]nums){//蓝色为最小值，或者最小值的右侧//红色为最小值左侧if(nums.length==1){returnnums[0];}intleft=0;intn=nums.length;intright=n-2;//n-1的位置必然是蓝色while(left<=right){intmid=(left+right)/2;if(nums[mid]<nums[n-1]){//[mid,n-1]为蓝色right=mid-1;}else{//[0,mid]为红色left=mid+1;}}returnnums[left];}}

33. 搜索旋转排序数组

整数数组 `nums` 按升序排列，数组中的值 **互不相同** 。 在传递给函数之前，`nums` 在预先未知的某个下标 `k`（`0 <= k < nums.length`）上进行了 **向左旋转**，使数组变为 `[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]`（下标 **从 0 开始** 计数）。例如， `[0,1,2,4,5,6,7]` 下标 `3` 上向左旋转后可能变为 `[4,5,6,7,0,1,2]` 。 给你 **旋转后** 的数组 `nums` 和一个整数 `target` ，如果 `nums` 中存在这个目标值 `target` ，则返回它的下标，否则返回 `-1` 。 你必须设计一个时间复杂度为 `O(log n)` 的算法解决此问题。

思路：1、根据红蓝染色法，蓝色表示target，或者target的右侧；红色表示target的左侧2、要判断mid和target是否在同一段，因为在同一段以及不同段的数组，染色的方式不同。3、如果mid和target在同一段即：ifmid<end，表示mid在后一段，那么mid>=target时 or target>end时，就能确定[mid,n-1]之间的区间是蓝色。ifmid>end,表示mid在前一段，那么mid>=target and target>end，才能保证[mid,n-1]之间的区间是蓝色。 其他的情况只能保证mid之前是红色。 ps:要注意nums[mid]>=target中的等号,如果去掉等号就不对了，因为mid==target时，不会把mid染成蓝色。 代码：classSolution{publicbooleanis_blue(intmid,int[]nums,inttarget){intn=nums.length;if(nums[mid]<nums[nums.length-1]){//mid在后半段returnnums[mid]>=target||target>nums[n-1];//[mid,n-1]是蓝色,要注意nums[mid]>=target中的等号}else{//mid 在前半段returnnums[mid]>=target&&target>nums[n-1];//[mid,n-1]是蓝色}}publicintsearch(int[]nums,inttarget){//蓝色表示target的右侧，红色表示target左侧//仍然是两段递增的数组intleft=0;intn=nums.length;intright=n-2;//n-1的位置要么是target，要么是target的右侧,是蓝色while(left<=right){intmid=(left+right)/2;if(is_blue(mid,nums,target)){//[mid,n-1]是蓝色已经确定right=mid-1;}else{//[0,mid]是红色已经确定left=mid+1;}}returntarget==nums[left]?left:-1;}}