Tuesday, June 9, 2015

leetcode Question: Find Peak Element

Practice daily, and train myself to know the algorithms better. Notes from April 8, 2015
"find peak element" question: A peak element is an element that is greater than its neighbors. For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.
So, the websites I read:
5. https://www.youtube.com/watch?v=HtSuA80QTyo  (MIT lecture, 53 minutes, really good one!)
So, I like to write something to help myself ace the question next practice. Using analysis, it may not perform under stress; how about memorization, it will not last after a few months.
Here, using a special case, an array in increasing order. Also, people can help you do analysis if you present a special test case, know where you are in the problem solving.
For example, the array, [1, 2,3,4,5,6,7,8,9], if we go through one by one, 9 is the peak number; but it takes 9 steps from checking 1, then 2, and last is 9. It is not efficient, O(n) steps. So, how to do log(n) step, first one is to check the middle number, 5; and then, 5 is not a peak element, then, analyze and conclude that: [6,7,8,9] has one peak element; and then, check number 8, which is not a peak element; [9] has a perk element. First check is number 5, last check is number 9, only 3 checks; 3 checks is 5, 8, 9.

No comments:

Post a Comment