注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex162 Find Peak Element  

2015-05-14 21:11:08|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
意思就是找到某个峰值就可以了,不要求全部。

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

click to show spoilers.

Note:

Your solution should be in logarithmic complexity.

题目的难点就在于需要o(logn)的复杂度,其实也很简单,直接分治呗!写的时候需要注意midIndex是否应该包含到下一次递归中,而且头尾下标需要重点考虑。

int traverse(int*nums, int numSize)
{
int midIndex = numSize / 2;
if (numSize == 1)
{
return 0;
}
if (numSize==2)
{
if (nums[0] > nums[1])
{
return 0;
}
else
{
return 1;
}
}
if ((nums[midIndex] > nums[midIndex - 1]) && (nums[midIndex] > nums[midIndex + 1]))
{
return midIndex;
}
else
{
int index1 = traverse(nums,midIndex+1);
if (index1 != -1&&index1!=midIndex)
return index1;
int index2 = traverse(nums+midIndex, numSize - midIndex);
index2 += midIndex; //这个地方需要注意一下,因为下标是从midIndex开始计算的
//所以下一次的时候需要恢复一下
if (index2 != -1 && index2 != midIndex)
return index2;
}
return -1;
}

int findPeakElement(int* nums, int numsSize) {

if (numsSize <= 0)
return -1;
if (numsSize == 1)
{
return 0;
}
return traverse(nums, numsSize);
}



second time 精简代码 

class Solution1 {
public:
int findPeakElement(vector<int>& nums)
{
if (nums.size() <= 1)
return 0;
return peakIndex(nums, 0, nums.size() - 1);
}

int peakIndex(vector<int>& nums, int begin, int end)
{
if (begin > end)
return -1;
int mid = (begin + end) / 2;
int left = (mid - 1) < 0 ? INT_MIN : nums[mid - 1];
int right = (mid + 1) > (nums.size() - 1) ? INT_MIN : nums[mid + 1];

if (nums[mid] > right && nums[mid] > left)
return mid;
if (mid > 0 && nums[mid - 1] > nums[mid])
return peakIndex(nums, begin, mid - 1);
else
return peakIndex(nums, mid + 1, end);
}
};

2015/12/2 更新一下java代码,非递归的

public class FindPeakElement {
public int findPeakElement(int[] nums) {
if (nums.length <= 0) {
return -1;
}
return helper(nums);
}
private int helper(int[] nums) {
int left = 0;
int right = nums.length - 1;
int mid = 0;
// 下面是binary search
//int leftVal = 0;
//int rightVal = 0;
long leftVal = 0;
long rightVal = 0;
// 这个地方不能是int 因为给的测试集合里面有一个[Integer.MIN_VALUE]
// 特别缺德
while (left <= right) {
mid = (left + right) / 2;
leftVal = (mid - 1) < 0 ? Long.MIN_VALUE : nums[mid - 1];
rightVal = (mid + 1) > nums.length - 1 ? Long.MIN_VALUE : nums[mid + 1];

if (leftVal < nums[mid] && rightVal < nums[mid]) {
return mid;
}

if (mid > 0 && nums[mid - 1] > nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}



  评论这张
 
阅读(10)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018