找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6790|回复: 14
收起左侧

[米群网刷题小分队] LeetCode新题 Find Peak Element

[复制链接]

9

主题

5

精华

316

积分

高级会员

Rank: 3Rank: 3

积分
316
发表于 12-5-2014 03:47 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 cpcs 于 12-5-2014 04:18 PM 编辑

求教一下各位大神面试的时候写这么多function会不会被鄙视。。。


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.
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.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.

  1. public class Solution {
  2.     private int[] arr;
  3.     public int findPeakElement(int[] num) {
  4.         arr = num;
  5.         return findPeak(0, num.length - 1);
  6.     }
  7.     private int findPeak(int from, int to) {
  8.         int mid = from + to >> 1;
  9.         if (isPeak(mid) == 0) return mid;
  10.         if (isPeak(mid) == -1) return findPeak (from, mid - 1);
  11.         else return findPeak(mid + 1, to);
  12.     }
  13.     private int isPeak(int i) {
  14.         if(biggerThanNext(i) && biggerThanPre(i)) return 0; //peak
  15.         if(biggerThanNext(i) && !biggerThanPre(i)) return -1; //down
  16.         else return 1; //up
  17.     }
  18.     private boolean biggerThanNext(int i) {
  19.         return i == arr.length - 1 || arr【i】 > arr[i + 1];
  20.     }
  21.     private boolean biggerThanPre(int i) {
  22.         return i == 0 || arr【i】 > arr[i - 1];
  23.     }
  24. }
复制代码


发表于 12-5-2014 04:05 PM | 显示全部楼层
贴一段c++的非递归的……

  1. class Solution {
  2. public:
  3.     int findPeakElement(const vector<int> &num) {
  4.         int n = num.size(), left = 0, right = n - 1;
  5.         while (left <= right) {
  6.             int mid = (left + right) >> 1;
  7.             if ((mid == 0) || (num[mid - 1] < num[mid])) {
  8.                 if ((mid + 1 == n) || (num[mid + 1] < num[mid])) {
  9.                     return mid;
  10.                 }   
  11.                 left = mid + 1;
  12.             }
  13.             else {
  14.                 right = mid - 1;
  15.             }
  16.             
  17.         }
  18.         return -1;
  19.     }
  20. };
复制代码
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
回复 支持 0 反对 1

使用道具 举报

发表于 12-5-2014 03:54 PM | 显示全部楼层
我帮您编辑了一下 顺便加个精。。。话说from + to >> 1要括号么。。。
回复 支持 反对

使用道具 举报

9

主题

5

精华

316

积分

高级会员

Rank: 3Rank: 3

积分
316
 楼主| 发表于 12-5-2014 03:58 PM | 显示全部楼层
cpcs 发表于 12-5-2014 03:54 PM
我帮您编辑了一下 顺便加个精。。。话说from + to >> 1要括号么。。。

谢谢曹神。。。格式又错了。已被自己蠢哭。
java里不用加括号,会先+再移位。
话说面试的时候可以写这么多function么。我觉得看起来好像好读一些。但是会让代码更长的样子。。。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表