• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

10 寻找山型数组的顶点(Maximum Number in Mountain Sequence)

开发技术 开发技术 5小时前 2次浏览

目录
  • 1 题目
  • 2 描述
  • 3 思路
    • 3.1 图解
    • 3.2 时间复杂度
    • 3.3 空间复杂度
  • 4 源码

1 题目

  寻找山型数组的顶点(Maximum Number in Mountain Sequence)

lintcode:题号——585,难度——medium

2 描述

  给定包含n 个整数的山脉数组,即先增后减的序列,找到山顶(最大值),数组严格递增、严格递减。

  样例1:

输入:nums = [1, 2, 4, 8, 6, 3]
输出:8

  样例2:

输入:nums = [10, 9, 8, 7]
输出:10

3 思路

  需要在一个先增后减的序列中寻找顶点值,类似爬山的过程,只要一直向上爬,顶点就在前面,身后的路不可能存在顶点,可以通过不断地抛掉一些区间,来缩小目标范围。
  之前的题目——第一个坏的版本[1]中,提到过二分法可以解决形如“ooooxxxx”的问题,本题无法将问题转化为这种形式,需要从另一个方面来思考,可以将整体拆解成“half half”型的两半,抛掉其中一半来缩小目标区间。
  使用二分法,取中点,如果中点是从左向右递增,则可以看成从左向右爬山,当前位置的左边则不可能存在顶点,抛掉左边区间;换个方向,如果中点是从右向左递增,则可以看成是从右向左爬山,当前位置的右边不可能存在顶点,抛掉右边区间。

  1. 取中点;
  2. 比较中点与下一个点的关系是递增还是递减,以此来判断顶点在哪一半区间;
  3. 抛掉不可能存在顶点的区间。
  4. 继续对剩下的区间执行以上步骤,直到找到顶点。

  过程中需要判断当前点的下一步是在向上走还是向下走,考虑下一个元素的时候可能会越界,套用之前的经典二分搜索模板[2],则可以不用考虑下一个元素是否越界的问题,因为start或mid之后一定存在end,退出条件是start + 1 < end不会出现访问越界的情况。

3.1 图解

graph TD
A –> A1[左边都比中点小,抛掉’1, 2′]
A[山型序列<br/>’1, 2, 4, 8, 6, 3′] — 中间位置元素’4′,下一个元素’8′,递增 –> B
B[缩小区间至’4, 8, 6, 3′] — 中间位置元素’8′,下一个元素’6′,递减 –> C
B –> B1[/右边都比中点小,抛掉’6, 3’/]
C[缩小区间至’4, 8′] — 只剩头尾元素比较大小 –> D
D(找到目标元素’8′)

3.2 时间复杂度

  算法的时间复杂度为O(log n)。

3.3 空间复杂度

  算法的空间复杂度为O(1)。

4 源码

  注意事项:

返回的是值,不是序号;

  C++版本:

/**
* @param nums: 参数
* @return: 返回值
*/
int findMin(vector<int> &nums) {
    int mountainSequence(vector<int> &nums) {
        // write your code here
        if (nums.empty())
        {
            return -1;
        }

        int start = 0;
        int end = nums.size() - 1;
        int mid = 0;
        while (start + 1 < end)
        {
            mid = start + (end - start) / 2;
            if (nums.at(mid) < nums.at(mid + 1))
            {
                start = mid;
            }
            if (nums.at(mid) > nums.at(mid + 1))
            {
                end = mid;
            }
        }

        if (nums.at(start) > nums.at(end))
        {
            return nums.at(start);
        }
        else
        {
            return nums.at(end);
        }
    }
}

  1. 第一个坏的版本:https://blog.csdn.net/SeeDoubleU/article/details/118370300 ↩︎

  2. 经典二分搜索:https://blog.csdn.net/SeeDoubleU/article/details/118271548 ↩︎


喜欢 (0)