文章目录
- 一、山脉数组的峰顶索引
- 二、枚举法
- 三、二分法
一、山脉数组的峰顶索引
https://leetcode.cn/problems/peak-index-in-a-mountain-array/description/
符合下列属性的数组 arr 称为 山脉数组 :
- arr.length >= 3
- 存在 i(0 < i < arr.length - 1)使得:
- arr[0] < arr[1] < … arr[i-1] < arr[i]
- arr[i] > arr[i+1] > … > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ,返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。
输入:arr = [0,10,5,2]
输出:1
山脉数组 就是 先增后减 的序列 , 山顶 就是最大值
上一篇博客 【算法】二分法 ① ( 二分法基本原理简介 | 二分法与哈希表对比 | 常见算法对应的时间复杂度 ) 中提到了常见的算法的时间复杂度如下 , 时间复杂度从小到大进行排序为 :
: 位运算 , 哈希表查询
: 二分法 , 快速幂算法 , 辗转相除法 , 倍增法 ;
: 枚举法 ,双指针算法 ;
: 快速排序 , 归并排序 , 堆排序 ;
: 枚举法 , 动态规划 ;
: 枚举法 , 动态规划 ;
: 组合相关的搜索问题 ;
: 排列相关的搜索问题 ;
解决该算法问题有两种方案 :
- 枚举法 : 从头到尾进行遍历一遍 ,
- 二分法 : 使用二分法遍历数组 , 时间复杂度
二、枚举法
代码示例 :
- 验证参数 : 任何函数都必须先 验证参数合法性 ;
- 枚举遍历 : 从头到尾进行遍历一遍 ,
- 算法逻辑 : 数组前半部分是递增的, array[i] < array[i + 1] , 如果遇到 array[i] > array[i + 1] 则说明 从 i 开始递减 , i 就是封顶索引 ;
class Solution {
public int peakIndexInMountainArray(int[] array) {
// 1. 验证参数合法性
if (array == null || array.length == 0) {
return -1;
}
// 2. 使用枚举法遍历数组元素
int index = -1;
for (int i = 1; i < array.length - 1; ++i) {
// 前半部分是递增的, array[i] < array[i + 1]
// 如果遇到 array[i] > array[i + 1] 从 i 开始递减
// i 就是封顶索引
if (array[i] > array[i + 1]) {
index = i;
break;
}
}
return index;
}
}
三、二分法
参考上一篇博客的 二分法模板 : 注意以下二分法的要点 ;
- ★ 要点一 : 循环控制变量 , 尽量不要使用 start <= end 或 start < end 作为循环判定条件 , 在某些情况下会执行失败 , 为了让程序有更多的适应性 , 这里使用 start + 1 < end 作为循环判定条件 , 可以有效避免死循环 ;
- ★ 要点二 : 取中间值的时候 , 尽量不要使用 (start + end) / 2 , 如果 两个数值都接近 Int.MAX_VALUE 则会溢出 ;
- ★ 要点三 : 缩小区间范围时 , 可以不需要 加减 1 ;
- 范围向左缩小 : 由于循环判定条件是 start + 1 < end , 范围缩小到中心点左侧时 , end 赋值可以不使用 mid - 1 , 直接使用 mid ;
- 范围向右缩小 : 由于循环判定条件是 start + 1 < end , 范围缩小到中心点左侧时 , start 赋值可以不使用 mid + 1 , 直接使用 mid ;
- ★ 要点四 : 循环完毕 , 判定 start 和 end 是不是要找的值 , 如果数组只有两个数的情况下 , while(start + 1 < end) 循环控制条件中的 start + 1 < end 直接为 false , 循环直接退出 , 此处判定一下 start 和 end 是不是要找的值 ;
参考的二分法模板 :
package cn.zkhw.schedule.utils;
public class Solution {
public int search(int[] nums, int target) {
// 1. 判断参数合法性
if(nums == null || nums.length == 0) {
return -1;
}
// 2. 二分查找的范围
int start = 0, end = nums.length - 1;
// 3. 开始循环进行二分查找
// 此处注意 start 和 end 区间需要能覆盖住所有目标值
// 该循环条件很重要 , 是通用模板
// ★ 要点一 : 此处尽量不要使用 start <= end 或 start < end 作为循环判定条件 , 在某些情况下会执行失败
// 为了让程序有更多的适应性 , 这里使用 start + 1 < end 作为循环判定条件 , 可以有效避免死循环
while(start + 1 < end) {
// 3.1 计算中间索引
// ★ 要点二 : 此处尽量不要使用 (start + end) / 2 , 如果 两个数值都接近 Int.MAX_VALUE 则会溢出
int mid = start + (end - start) / 2;
// 3.2 对比中间元素与目标值
if(nums[mid] == target) {
// 如果 中心元素 = 目标值 , 找到了目标元素的第一个位置
end = mid;
} else if(nums[mid] > target) {
// 如果 中心元素 > 目标值 , 则需要去 该查找区间的 左侧继续查找
// ★ 要点三 : 由于循环判定条件是 start + 1 < end , 此处 end 赋值可以不使用 mid - 1
end = mid;
} else {
// 如果 中心元素 < 目标值 , 则需要去 该查找区间的 右侧继续查找
// ★ 要点四 : 由于循环判定条件是 start + 1 < end , 此处 start 赋值可以不使用 mid + 1
start = mid;
}
}
// 4. ★ 要点五 : 循环完毕 , 判定 start 和 end 是不是要找的值
// 如果数组只有两个数的情况下
// while(start + 1 < end) 循环控制条件中的 start + 1 < end 直接为 false
// 循环直接退出 , 此处判定一下 start 和 end 是不是要找的值
if(nums[start] == target) {
return -1;
}
if(nums[end] == target) {
return -1;
}
// 5. 没有找到目标值
return -1;
}
}
根据二分法模板写出的 山脉数组的峰顶索引 算法 :
class Solution {
public int peakIndexInMountainArray(int[] array) {
// 1. 验证参数合法性
if (array == null || array.length == 0) {
return -1;
}
// 2. 二分查找的范围
int start = 1, end = array.length - 2, index = 0;
// 3. 开始循环进行二分查找
// 此处注意 start 和 end 区间需要能覆盖住所有目标值
// 该循环条件很重要 , 是通用模板
// ★ 要点一 : 此处尽量不要使用 start <= end 或 start < end 作为循环判定条件 , 在某些情况下会执行失败
// 为了让程序有更多的适应性 , 这里使用 start + 1 < end 作为循环判定条件 , 可以有效避免死循环
while (start + 1 < end) {
// 3.1 计算中间索引
// ★ 要点二 : 此处尽量不要使用 (start + end) / 2 , 如果 两个数值都接近 Int.MAX_VALUE 则会溢出
int mid = start + (end - start) / 2;
// 3.2 对比中间元素与目标值
if (array[mid] > array[mid + 1]) {
index = mid;
// ★ 要点三 : 由于循环判定条件是 start + 1 < end , 此处 end 赋值可以不使用 mid - 1
end = mid;
} else {
// ★ 要点四 : 由于循环判定条件是 start + 1 < end , 此处 start 赋值可以不使用 mid + 1
start = mid;
}
}
// 4. ★ 要点五 : 循环完毕 , 判定 start 和 end 是不是要找的值
// 如果数组只有两个数的情况下
// while(start + 1 < end) 循环控制条件中的 start + 1 < end 直接为 false
// 循环直接退出 , 此处判定一下 start 和 end 是不是要找的值
if(array[start] > array[start + 1]) {
return start;
}
if(array[end] > array[end + 1]) {
return end;
}
return index;
}
}