利用万网做网站,建设人力资源服务网站工作方案,短链生成,教育网站建设 思维导图说明
此文是课程https://edu.csdn.net/course/detail/38771 的讲义。
源码下载#xff1a;https://download.csdn.net/download/he_zhidan/88458478 题目
长度为n的数组nums#xff0c;请返回任意一峰值的索引。符合以下条件之一i便是峰值的索引。 n等于1 i等于0 nhttps://download.csdn.net/download/he_zhidan/88458478 题目
长度为n的数组nums请返回任意一峰值的索引。符合以下条件之一i便是峰值的索引。 n等于1 i等于0 n1 i等于0 nums[i] nums[i1] n1 i等于n-1 nums[i] nums[i-1] 0in-1 nums[i]nums[i-1] nums[i]nums[i1]
题目保证nums[i]不等于nums[i1]。
分析
假定
nums[left,r)符合nums[left]nums[left-1]且nums[r-1]nums[r]。显然初始情况nums[0,n)符合。
推论一如果[left,r)的长度为1则left就是返回的索引。
推论二假定left midr。如果mid[mid] mid[mid-1],则nums[mid,r)也符合假定。如果mid[mid] mid[mid-1]则nums[left,mid)也符合假定。
推论三推论二也可以也可以理解成分别抛弃[left,mid)和[mid,r)。令mid left(r-left)/2由于r-left2所以leftmidr。也就是抛弃的子数组不会为空。也就是数组不断变短。等长度为1结束。
时间复杂度
由于每次抛弃一半所以需要抛弃logn次。故时间复杂度O(logn)
核心代码
class Solution {
public: int findPeakElement(vectorint nums) { int left 0, r nums.size(); while (r - left 1) { const int mid left (r - left) / 2; if (nums[mid] nums[mid - 1]) { left mid; } else { r mid; } } return left; }
};
测试用例
int main()
{ Solution slu; vectorint nums { 1,2,3,4 }; int res slu.findPeakElement(nums); assert(3 res); nums { 4,3,2,1 }; res slu.findPeakElement(nums); assert(0 res); nums { 2,5,3,1 }; res slu.findPeakElement(nums); assert(1 res);
} 其它
学院课程 基础算法的C实现课程请点击下面的CSDN学院的链接。 2024年1月15之前完全免费之后绝大部分免费 https://edu.csdn.net/course/detail/38771 C#入职培训 此课程的目的让新同事更快完成从学生到C#程序员的转换更快上手完成C#的开发工作。 https://edu.csdn.net/course/detail/38768 C入职培训 让新同事更快完成从学生到C程序员的转换更快上手完成C的开发工作。 https://edu.csdn.net/course/detail/32049
运行验证环境
Win10 VS2022 Ck17 或win7 VS2019 C17 每天都补充正能量 好好学习天天向上。 事无终始无务多业。 是故置本不安者无务丰末。
相关下载
如果你时间宝贵只想看精华请到CSDN下载频道下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
