建设展示型网站公司哪家好,ps做网站导航条高度,wordpress 去除底部,旅游攻略的网站怎么做题目
162. 寻找峰值峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums#xff0c;找到峰值元素并返回其索引。数组可能包含多个峰值#xff0c;在这种情况下#xff0c;返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] nums[n] -∞ 。你必须实现时…题目
162. 寻找峰值峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回 任何一个峰值 所在位置即可。你可以假设 nums[-1] nums[n] -∞ 。你必须实现时间复杂度为 O(log n) 的算法来解决此问题。1 nums.length 1000-2 ^ 31 nums[i] 2 ^ 31 - 1对于所有有效的 i 都有 nums[i] ! nums[i 1]
解法
Java 二分
第 1 步
首先时间复杂度为 Ologn可以联想到 二分/二叉树 类似的做法如果是二分则需要具备单调性
第 2 步
我们考虑数组可能出现的情况抽象出来分为四种递增、递减、先减后增、先增后减其他情况都是这四种的组合
第 3 步
分析四种情况 递增则最后一个元素一定满足因为大于前一个元素、且大于 nums[n] -∞递减则第一个元素一定满足因为大于后一个元素、且大于 nums[0] -∞先减后增则第一个或者最后一个元素均满足如上先增后减则增的那段最后一个元素也是减的那段第一个元素满足 可以总结下递增那段最后一个元素递减那段第一个元素
第 4 步
因此模拟二分 如果 nums[mid] nums[mid1] 先判断 mid不满足则区间左侧满足如果 nums[mid] nums[mid1] 先判断 mid 1不满足则区间右侧满足 时间复杂度Ologn空间复杂度O1
代码
/*** Java 二分** 第 1 步* 首先时间复杂度为 Ologn可以联想到 二分/二叉树 类似的做法* 如果是二分则需要具备单调性** 第 2 步* 我们考虑数组可能出现的情况抽象出来分为四种递增、递减、先减后增、先增后减* 其他情况都是这四种的组合** 第 3 步* 分析四种情况* * 递增则最后一个元素一定满足因为大于前一个元素、且大于 nums[n] -∞* * 递减则第一个元素一定满足因为大于后一个元素、且大于 nums[0] -∞* * 先减后增则第一个或者最后一个元素均满足如上* * 先增后减则增的那段最后一个元素也是减的那段第一个元素满足* 可以总结下递增那段最后一个元素递减那段第一个元素** 第 4 步* 因此模拟二分* * 如果 nums[mid] nums[mid1] 先判断 mid不满足则区间左侧满足* * 如果 nums[mid] nums[mid1] 先判断 mid 1不满足则区间右侧满足* 时间复杂度Ologn空间复杂度O1**/
public int findPeakElement(int[] nums) {int left 0;int right nums.length - 1;int res left;while (left right) {int mid ((right - left) 1) left;if (nums[mid] nums[mid 1]) {right mid - 1;if (mid 0 || nums[mid] nums[mid - 1]) {res mid;}} else {left mid 1;if (mid 1 nums.length - 1 || nums[mid 1] nums[mid 2]) {res mid 1;}}}return res;
}
