3 寻找峰值

题目描述;

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。

1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

2.假设 nums[-1] = nums[n] = −∞

3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

4.你可以使用O(logN)的时间复杂度实现此问题吗？

数据范围：

1≤nums.length≤2×10^5

−2^31<=nums[i]<=2^31−1

如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：

示例1:

输入：[2,4,1,2,7,8,4]

返回值：1

说明：4和8都是峰值元素，返回4的索引1或者8的索引5都可以

示例2：

输入：[1,2,3,1]

返回值：2

说明：3 是峰值元素，返回其索引 2

解题思路：

题目要求时间复杂度为O(logN)，所以暴力求解肯定不行，因为题目将数组边界看成最小值，而我们只需要找到其中一个波峰，因此只要不断地往高处走，一定会有波峰。那我们可以每次找一个标杆元素，将数组分成两个区间，每次就较高的一边走，因此也可以用分治来解决，而标杆元素可以选择区间中点。

如果中间值大于它右边的值：我们不妨举个例子[x,x,x,5,4,x,x],其中x为任意值，我们可以带入一些值进去发现右边是不一定有坡峰的，如[x,x,x,5,4,5,4](有坡峰）[x,x,x,5,4,3,2](无坡峰），这也好解释由于右边是往下走的所以不能够确定峰值。但是左边一定是会有峰值的，同理我们可以来分析如果左边值是逐渐递减的如[9,8,6,5,4,x,x],我们可以知道9就是峰值，如果索引为2的值只要小于5那么5就是峰值，如果索引为2的值大于5那么索引为1的值如果小于索引为2的话索引为2就是峰值，否则索引为0的值如果大于索引为1的话索引为0就是峰值，否则索引为1的就是峰值。（这里关系比较复杂，大家可以自己去推推)。

同理如果中间值小于右边的元素，说明此时往右是向上，向上一定能有波峰。

动图展示：

具体代码：

int findPeakElement(int* nums, int numsLen ) {
    // write code here
    int left=0;
    int right=numsLen-1;
    while(left<right)
    {
        int mid=(left+right)/2;
        if(nums[mid]>nums[mid+1])
        {
            right=mid;
        }
        else
        {
            left=mid+1;
        }
    }
    return left;
}

注意事项：

1. while循环中没有加=，加了=后会出错
2. 往高处走一定有坡峰，当nums[mid]>nums[mid+1]时，中间值更大，所以向左缩短区间，nums[mid]<nums[mid+1]时，中间值右边更大，所以向右缩短区间。

4 二维数组的查找

题目描述：

在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

[

[1,2,8,9],

[2,4,9,12],

[4,7,10,13],

[6,8,11,15]

]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 0≤n,m≤5000， 矩阵中的值满足 0≤val≤10^9

进阶：空间复杂度 O(1)，时间复杂度 O(n+m)

示例1：

输入：7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值：true

说明:存在7，返回true

示例2：

输入：1,[[2]]

返回值：false

说明：不存在1，返回false

示例3：

输入：3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值：false

说明：不存在3，返回false

解题思路：

这道题常规遍历肯定是行不通的，我们可以考虑用二分查找的思维来做题，二分查找就是不断的缩小区间直至我们找到我们想要找到的数据，我们通过题目描述不难发现这个二维数组其实就是一个杨氏矩阵（行从左到右依次递增，列从上到下依次递增），我们可以紧紧抓住这个条件，首先将数据定位到最右上边的元素（左下也行），如果要查找的元素比右上边的元素还大，那我们就可以排除这一行了，如果要查找的元素比右上边的元素还小，那么就可以排除这一列，然后迭代的走下去，注意控制循环结束的条件。

动图展示：

具体代码：

bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    // write code here
    int row=0;
    int col=*arrayColLen-1;
    while(row < arrayRowLen  && col >= 0)
    {
        if(array[row][col] > target)
        {
            col--;
        }
        else if(array[row][col] < target)
        {
            row++;
        }
        else 
        {
            return true;
        }
    }
    return false;
}

注意事项：

循环结束的条件要控制好。

结语

与二分查找相关的题目还有很多，但是终归这些题都是在如何利用已知条件来转换成我们所熟悉的二分方法，如果觉得博主的文章对你有帮助的话可不可以3连支持一下，后面博主还会持续更新剑指offer上的有关题目。