【算法】二分法 ③ ( 山脉数组的峰顶索引 | 枚举法 | 二分法 )

2023-03-30 18:56:52 浏览数 (1)

文章目录

  • 一、山脉数组的峰顶索引
  • 二、枚举法
  • 三、二分法

一、山脉数组的峰顶索引

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

山脉数组 就是 先增后减 的序列 , 山顶 就是最大值 , 本题目求的是 最大值的索引 ;

上一篇博客 【算法】二分法 ① ( 二分法基本原理简介 | 二分法与哈希表对比 | 常见算法对应的时间复杂度 ) 中提到了常见的算法的时间复杂度如下 , 时间复杂度从小到大进行排序为 :

O(1)

: 位运算 , 哈希表查询

O(log n)

: 二分法 , 快速幂算法 , 辗转相除法 , 倍增法 ;

O(n)

: 枚举法 , 单调栈算法 , 双指针算法 ;

O(n log n)

: 快速排序 , 归并排序 , 堆排序 ;

O(n^2)

: 枚举法 , 动态规划 ;

O(n^3)

: 枚举法 , 动态规划 ;

O(2^n)

: 组合相关的搜索问题 ;

O(n!)

: 排列相关的搜索问题 ;

解决该算法问题有两种方案 :

  • 枚举法 : 从头到尾进行遍历一遍 , 时间复杂度
O(n)

;

  • 二分法 : 使用二分法遍历数组 , 时间复杂度
O(log n)

;

二、枚举法

代码示例 :

  • 验证参数 : 任何函数都必须先 验证参数合法性 ;
  • 枚举遍历 : 从头到尾进行遍历一遍 , 时间复杂度
O(n)

;

  • 算法逻辑 : 数组前半部分是递增的, array[i] < array[i 1] , 如果遇到 array[i] > array[i 1] 则说明 从 i 开始递减 , i 就是封顶索引 ;
代码语言：javascript复制
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 是不是要找的值 ;

参考的二分法模板 :

代码语言：javascript复制
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;
    }
}

根据二分法模板写出的 山脉数组的峰顶索引 算法 :

代码语言：javascript复制
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;
    }
}
遍历 排序 数组 算法 索引

0 人点赞