二刷 05/2022
Version #1 Binary Search
Time O(logN)
Space O(1)
Runtime: 0 ms, faster than 100.00% of Java online submissions for Peak Index in a Mountain Array.
Memory Usage: 46.7 MB, less than 20.35% of Java online submissions for Peak Index in a Mountain Array.
class Solution {
public int peakIndexInMountainArray(int[] arr) {
if (arr == null || arr.length < 3) {
return -1;
}
int start = 0, end = arr.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (arr[mid] < arr[mid + 1]) {
start = mid + 1;
} else {
end = mid;
}
}
if (arr[start] > arr[end]) {
return start;
}
return end;
}
}
Version #1 Binary Search
二分法的条件，不一定是left/right和mid比，找peak也可以是mid和自己左右比
[2ND TRY]
33.69 %
Should always take care of out of boundary exception
class Solution {
public int peakIndexInMountainArray(int[] A) {
int start = 0;
int end = A.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (mid != 0 && A[mid - 1] < A[mid] && A[mid] > A[mid + 1]) return mid;
if (mid == 0 || A[mid - 1] < A[mid]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return start;
}
}
[1ST TRY]
class Solution {
public int peakIndexInMountainArray(int[] A) {
int left = 0;
int right = A.length - 1;
int mid = 0;
while (left < right) {
mid = left + (right - left) / 2;
if (A[mid] < A[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
Version #2 One Pass
8.24 %
class Solution {
public int peakIndexInMountainArray(int[] A) {
int left = 0;
int right = A.length - 1;
while (left + 1 < right && A[left] < A[left + 1]) left++;
while (right - 1 > left && A[right] < A[right - 1]) right--;
return left;
}
}
No comments:
Post a Comment