企业官网建设流程全解析

织梦wap网站,网站推广的方法,哪做网站比较好,做网站一般收取多少钱LeetCode 面试经典 150_二分查找_寻找峰值#xff08;113_162_C_中等#xff09;题目描述#xff1a;输入输出样例#xff1a;题解#xff1a;解题思路#xff1a;思路一#xff08;暴力破解#xff09;#xff1a;思路二#xff08;二分查找#xff09;#xff1a…LeetCode 面试经典 150_二分查找_寻找峰值113_162_C_中等题目描述输入输出样例题解解题思路思路一暴力破解思路二二分查找代码实现代码实现思路一暴力破解代码实现思路二二分查找以思路一为例进行调试题目描述峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回任何一个峰值所在位置即可。你可以假设 nums[-1] nums[n] -∞ 。你必须实现时间复杂度为 O(log n) 的算法来解决此问题。输入输出样例示例 1输入nums [1,2,3,1]输出2解释3 是峰值元素你的函数应该返回其索引 2。示例 2输入nums [1,2,1,3,5,6,4]输出1 或 5解释你的函数可以返回索引 1其峰值元素为 2或者返回索引 5 其峰值元素为 6。提示1 nums.length 1000-231 nums[i] 231- 1对于所有有效的 i 都有 nums[i] ! nums[i 1]题解解题思路思路一暴力破解1、利用 对于所有有效的 i 都有nums[i] ! nums[i 1]那最大值必定为峰值。返回任何一个峰值所在位置即可。2、复杂度分析① 时间复杂度O(n)n 为数组中元素的个数只遍历了一遍数组中的元素。② 空间复杂度O(1)。思路二二分查找1、利用 对于所有有效的 i 都有nums[i] ! nums[i 1]。运用一个结论当 nums[i]nums[i1] 时 【i1 ~ nums.size()-1】 必定有峰值反之 0~i 必定有峰值。返回任何一个峰值所在位置即可例 nums[1,2,3,4,2,1] 34 那么 4 到最后一定有峰值。2、复杂度分析① 时间复杂度O(logn)其中 n 为 nums 的长度。② 空间复杂度O(1)。代码实现代码实现思路一暴力破解classSolution1{public:// 函数 findPeakElement 接受一个整数向量 nums并返回一个峰值元素的索引intfindPeakElement(vectorintnums){intid-1;// 初始化 id 为 -1表示当前没有找到峰值longlongmaxNum-2147483649;// 初始化 maxNum 为一个非常小的数比最小的 int 还小// 遍历 nums 向量中的每个元素for(inti0;inums.size();i){// 如果当前元素 nums[i] 大于 maxNumif(nums[i]maxNum){// 更新 id 为当前索引 iidi;// 更新 maxNum 为当前元素 nums[i]maxNumnums[i];}}// 返回找到的峰值元素的索引 idreturnid;}};代码实现思路二二分查找classSolution2{// 利用二分查找的原理来寻找峰值元素// 结论如果 nums[i] nums[i1]那么 i1 到 nums.size()-1 的范围内必定存在峰值// 如果 nums[i] nums[i1]那么 0 到 i 的范围内必定存在峰值// 因此可以通过比较中间元素与其右侧相邻元素的大小来进行二分搜索public:// 函数 findPeakElement 接受一个整数向量 nums并返回找到的峰值元素的索引intfindPeakElement(vectorintnums){intleft0;// 初始化左边界intrightnums.size()-1;// 初始化右边界// 当左边界小于右边界时继续查找while(leftright){// 计算中间索引 mid避免溢出intmidleft(right-left)/2;// 比较中间元素 nums[mid] 和其右侧元素 nums[mid 1]if(nums[mid]nums[mid1]){// 如果 mid 位置的元素大于其右侧元素意味着峰值可能在 mid 或者左侧rightmid;// 显示更新右边界}else{// 如果 mid 位置的元素小于其右侧元素意味着峰值一定在右侧leftmid1;// 更新左边界}}// 当左边界与右边界相遇时left 位置即为我们找到的峰值元素索引returnleft;}};以思路一为例进行调试#includeiostream#includevectorusingnamespacestd;classSolution1{public:// 函数 findPeakElement 接受一个整数向量 nums并返回一个峰值元素的索引intfindPeakElement(vectorintnums){intid-1;// 初始化 id 为 -1表示当前没有找到峰值longlongmaxNum-2147483649;// 初始化 maxNum 为一个非常小的数比最小的 int 还小// 遍历 nums 向量中的每个元素for(inti0;inums.size();i){// 如果当前元素 nums[i] 大于 maxNumif(nums[i]maxNum){// 更新 id 为当前索引 iidi;// 更新 maxNum 为当前元素 nums[i]maxNumnums[i];}}// 返回找到的峰值元素的索引 idreturnid;}};intmain(){vectorintnums{1,2,3,1};Solution1 s;couts.findPeakElement(nums);return0;}LeetCode 面试经典 150_二分查找_寻找峰值113_162)原题链接欢迎大家和我沟通交流(✿◠‿◠)