题目简述 LeetCode 852
Let's call an array A a mountain if the following properties hold:
A.length >= 3- There exists some
0 < i < A.length - 1such thatA[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
Example 1:
Input: [0,1,0]
Output: 1
Example 2:
Input: [0,2,1,0]
Output: 1
Note:
3 <= A.length <= 100000 <= A[i] <= 10^6- A is a mountain, as defined above.
解题思路
思路１
- 从前往后依次比较，遇到第一个后者比前者小的，输出前者的下标
思路１
- 折半查找
Code
思路１ -> Code
# include<stdio.h>
int peakIndexInMountainArray(int* A, int ASize)
{
int i, index;
for (i = 0; i < ASize - 1; i ++)
{
if(A[i + 1] < A[ i ])
{
index = i;
break;
}
}
return index;
}
int main()
{
// int a[10] = {0, 1, 0};
int a[10] = {0, 2, 1, 0};
printf("%d \n", peakIndexInMountainArray(a, 4));
}
思路２ -> Code
# include<stdio.h>
int peakIndexInMountainArray(int* A, int ASize)
{
int left = 0, right = ASize - 1;
int mid;
while(left < right)
{
mid = left + (right - left) / 2;
if(A[mid] < A[mid + 1])
{
left = mid + 1;
}
else
{
right = mid;
}
}
return left;
}
int main()
{
// int a[10] = {0, 1, 0};
int a[10] = {0, 2, 1, 0};
printf("%d \n", peakIndexInMountainArray(a, 4));
}
总结
- 两种思路时间都为 4ms
