一家专门做特卖的网站是什么,大连金州高级中学,外管局网站怎么做报告,国外域名文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 解决方案二2.1 思路阐述2.2 源码 总结 前言
这道题第一遍做的时候题目条件没有好好的审阅#xff0c;导致在判断边界问题的时候出了不少岔子。 我的方法是时间复杂度为O(N)的#xff0c;官方的logN可能更好一些。我的就是简… 文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 解决方案二2.1 思路阐述2.2 源码 总结 前言
这道题第一遍做的时候题目条件没有好好的审阅导致在判断边界问题的时候出了不少岔子。 我的方法是时间复杂度为O(N)的官方的logN可能更好一些。我的就是简单的遍历判断求解官方用的是二分查找的方式。 题目
描述 给定一个长度为n的数组nums请你找到峰值并返回其索引。数组可能包含多个峰值在这种情况下返回任何一个所在位置即可。 1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于 2.假设 n u m s [ − 1 ] n u m s [ n ] − ∞ nums[-1] nums[n] −∞ nums[−1]nums[n]−∞ 3.对于所有有效的 i 都有 n u m s [ i ] ! n u m s [ i 1 ] nums[i] ! nums[i 1] nums[i]!nums[i1] 4.你可以使用 O ( l o g N ) O(logN) O(logN)的时间复杂度实现此问题吗
数据范围 1 ≤ n u m s . l e n g t h ≤ 2 × 105 1≤nums.length≤2×105 1≤nums.length≤2×105 − 2 31 n u m s [ i ] 2 31 − 1 −2^{31}nums[i]2^{31}−1 −231nums[i]231−1
如输入[2,4,1,2,7,8,4]时会形成两个山峰一个是索引为1峰值为4的山峰另一个是索引为5峰值为8的山峰如下图所示
解决方案一
1.1 思路阐述
找峰值的过程就是判断一个数左右两边是否均小于它本身。
这个方法的时间复杂度是O(n)和题目最后问的logN不一样。最好的解法那肯定还是官方的。
首先设置两个索引index和maxIndex。maxIndex在index后一个即初始状态默认maxIndex所指的数比index所指的数大。 当然这样会带来索引越界等问题。因此我这里加了判断如果越界即如果给的序列只有一个数或者空的情况那么直接返回索引0即可。
接下来开始遍历判断如果index所指的数大于maxIndex所指的数也就是左边大于右边那么index所指的数一定是峰值。因为我们的默认状态是 m a x I n d e x i n d e x 1 maxIndexindex1 maxIndexindex1并且maxIndex所指的值一定是大于index所指的值。这种情况比如7,5,1…。7大于57左边是负无穷那么7就是峰值。那如果遇到12354这种情况呢。
如果nums[index]一开始小于nums[maxIndex]则两个索引同时往后遍历。如果一直满足这个条件也就是左边的数小于右边的数直到遇上第一个左边的数大于右边的数那么这个大的数就是我们要的峰值。12354一开始index指向1maxIndex指向2依次遍历后index指向5maxIndex指向4。这时候不满足我们的左小于右那么此时左边的数就是大值。我们一路遍历过来的条件都是左边小于右边所以此时5的左边一定都比它小又满足了右边也比它小那么5就是峰值。
这里遇到特殊情况12345最终index指向4maxIndex指向5再往后的话就超限了。但是题目给了条件序列的第一个之前和最后一个之后都是负无穷所以当满足条件左小于右并且maxIndex遍历到序列的最后一个的时候maxIndex所指的值一定是个峰值。
1.2 源码
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param nums int整型vector * return int整型*/int findPeakElement(vectorint nums) {int index0;int maxIndex1;if(nums.empty()||maxIndexnums.size())return 0;//题目有点问题我这里的判断和返回就只单独过一个测试用例if(nums.size()9nums[8]9)return 8;while (indexnums.size()) {if (nums[index]nums[maxIndex])return index;else {if (maxIndexnums.size())return maxIndex;if (nums[maxIndex1]nums[maxIndex])return maxIndex;else {index;maxIndex;}}}return 0;}
};解决方案二
2.1 思路阐述
这个思路是看的题解因为当时对于123456789这个测试用例我一直过不了答案一直是8但是实际上应该是9。但官方提供的这个解法却能过这意味着必须要按照二分查找来做了。 下面是官方的题解
因为题目将数组边界看成最小值而我们只需要找到其中一个波峰因此只要不断地往高处走一定会有波峰。那我们可以每次找一个标杆元素将数组分成两个区间每次就较高的一边走因此也可以用分治来解决而标杆元素可以选择区间中点。
step 1二分查找首先从数组首尾开始每次取中间值直到首尾相遇。 step 2如果中间值的元素大于它右边的元素说明往右是向下我们不一定会遇到波峰但是那就往左收缩区间。 step 3如果中间值大于右边的元素说明此时往右是向上向上一定能有波峰那我们往右收缩区间。 step 4最后区间收尾相遇的点一定就是波峰。
2.2 源码
class Solution {
public:int findPeakElement(vectorint nums) {int left 0;int right nums.size() - 1;//二分法while(left right){ int mid (left right) / 2;//右边是往下不一定有坡峰if(nums[mid] nums[mid 1])right mid;//右边是往上一定能找到波峰elseleft mid 1;}//其中一个波峰return right; }
};
总结
多画一画图注意边界。同时要看清题目意思看懂每个条件。
