Skip to content

Commit 34f6fd6

Browse files
fishercoder1534fishercoder1534
committed
update 162
1 parent 2624c2d commit 34f6fd6

File tree

2 files changed

+76
-104
lines changed

2 files changed

+76
-104
lines changed

‎src/main/java/com/fishercoder/solutions/_162.java

+39-74
Original file line numberDiff line numberDiff line change
@@ -1,84 +1,49 @@
11
package com.fishercoder.solutions;
22

3-
/**
4-
* 162. Find Peak Element
5-
6-
A peak element is an element that is greater than its neighbors.
7-
8-
Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.
9-
10-
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
11-
12-
You may imagine that nums[-1] = nums[n] = -∞.
13-
14-
Example 1:
15-
Input: nums = [1,2,3,1]
16-
Output: 2
17-
Explanation: 3 is a peak element and your function should return the index number 2.
18-
19-
Example 2:
20-
Input: nums = [1,2,1,3,5,6,4]
21-
Output: 1 or 5
22-
Explanation: Your function can return either index number 1 where the peak element is 2,
23-
or index number 5 where the peak element is 6.
24-
25-
Note:
26-
Your solution should be in logarithmic complexity.
27-
*/
28-
293
public class _162 {
304

31-
public static class Solution1 {
32-
/**
33-
* credit: https://discuss.leetcode.com/topic/29329/java-solution-and-explanation-using-invariants
34-
*
35-
* Basically, we need to keep this invariant:
36-
* nums[left] > nums[left-1], then we could return left as the result
37-
* or nums[right] > nums[right+1], then we could return right as the result
38-
*
39-
* Time: O(Ologn)
40-
*/
41-
public int findPeakElement(int[] nums) {
42-
if (nums == null || nums.length == 0) {
43-
return 0;
44-
}
45-
int left = 0;
46-
int right = nums.length - 1;
47-
while (left + 1 < right) {
48-
int mid = left + (right - left) / 2;
49-
if (nums[mid] < nums[mid + 1]) {
50-
left = mid;
51-
} else {
52-
right = mid;
5+
public static class Solution1 {
6+
/**
7+
* credit: https://discuss.leetcode.com/topic/29329/java-solution-and-explanation-using-invariants
8+
* <p>
9+
* Basically, we need to keep this invariant:
10+
* nums[left] > nums[left-1], then we could return left as the result
11+
* or nums[right] > nums[right+1], then we could return right as the result
12+
* <p>
13+
* Time: O(logn)
14+
*/
15+
public int findPeakElement(int[] nums) {
16+
if (nums == null || nums.length == 0) {
17+
return 0;
18+
}
19+
int left = 0;
20+
int right = nums.length - 1;
21+
while (left + 1 < right) {
22+
int mid = left + (right - left) / 2;
23+
if (nums[mid] < nums[mid + 1]) {
24+
left = mid;
25+
} else {
26+
right = mid;
27+
}
28+
}
29+
return (left == nums.length - 1 || nums[left] > nums[left + 1]) ? left : right;
5330
}
54-
}
55-
return (left == nums.length - 1 || nums[left] > nums[left + 1]) ? left : right;
5631
}
57-
}
5832

59-
public static class Solution2 {
60-
/**
61-
* My original O(n) solution.
62-
*/
63-
public int findPeakElement(int[] nums) {
64-
if (nums == null || nums.length == 0) {
65-
return 0;
66-
}
67-
int n = nums.length;
68-
int result = 0;
69-
for (int i = 0; i < n; i++) {
70-
if (i == 0 && n > 1 && nums[i] > nums[i + 1]) {
71-
result = i;
72-
break;
73-
} else if (i == n - 1 && i > 0 && nums[i] > nums[i - 1]) {
74-
result = i;
75-
break;
76-
} else if (i > 0 && i < n - 1 && nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
77-
result = i;
78-
break;
33+
public static class Solution2 {
34+
/**
35+
* My original O(n) solution.
36+
*/
37+
public int findPeakElement(int[] nums) {
38+
for (int i = 1; i < nums.length; i++) {
39+
if (nums[i] > nums[i - 1] && i + 1 < nums.length && nums[i] > nums[i + 1]) {
40+
return i;
41+
}
42+
if (i == nums.length - 1 && nums[i] > nums[i - 1]) {
43+
return i;
44+
}
45+
}
46+
return 0;
7947
}
80-
}
81-
return result;
8248
}
83-
}
8449
}

‎src/test/java/com/fishercoder/_162Test.java

+37-30
Original file line numberDiff line numberDiff line change
@@ -7,34 +7,41 @@
77
import static org.junit.Assert.assertEquals;
88

99
public class _162Test {
10-
private static _162.Solution1 solution1;
11-
private static _162.Solution2 solution2;
12-
private static int[] nums;
13-
14-
@BeforeClass
15-
public static void setup() {
16-
solution1 = new _162.Solution1();
17-
solution2 = new _162.Solution2();
18-
}
19-
20-
@Test
21-
public void test1() {
22-
nums = new int[] {1, 2};
23-
assertEquals(1, solution1.findPeakElement(nums));
24-
assertEquals(1, solution2.findPeakElement(nums));
25-
}
26-
27-
@Test
28-
public void test2() {
29-
nums = new int[] {1};
30-
assertEquals(0, solution1.findPeakElement(nums));
31-
assertEquals(0, solution2.findPeakElement(nums));
32-
}
33-
34-
@Test
35-
public void test3() {
36-
nums = new int[] {1, 2, 3, 1};
37-
assertEquals(2, solution1.findPeakElement(nums));
38-
assertEquals(2, solution2.findPeakElement(nums));
39-
}
10+
private static _162.Solution1 solution1;
11+
private static _162.Solution2 solution2;
12+
private static int[] nums;
13+
14+
@BeforeClass
15+
public static void setup() {
16+
solution1 = new _162.Solution1();
17+
solution2 = new _162.Solution2();
18+
}
19+
20+
@Test
21+
public void test1() {
22+
nums = new int[]{1, 2};
23+
assertEquals(1, solution1.findPeakElement(nums));
24+
assertEquals(1, solution2.findPeakElement(nums));
25+
}
26+
27+
@Test
28+
public void test2() {
29+
nums = new int[]{1};
30+
assertEquals(0, solution1.findPeakElement(nums));
31+
assertEquals(0, solution2.findPeakElement(nums));
32+
}
33+
34+
@Test
35+
public void test3() {
36+
nums = new int[]{1, 2, 3, 1};
37+
assertEquals(2, solution1.findPeakElement(nums));
38+
assertEquals(2, solution2.findPeakElement(nums));
39+
}
40+
41+
@Test
42+
public void test4() {
43+
nums = new int[]{1, 2, 1, 3, 5, 6, 4};
44+
assertEquals(5, solution1.findPeakElement(nums));
45+
assertEquals(1, solution2.findPeakElement(nums));
46+
}
4047
}

0 commit comments

Comments
 (0)