四刷 06/2022
Version #1 One Pass Binary Search
先判断哪边有序
Time O(logN)
Space O(1)
Runtime: 1 ms, faster than 70.07% of Java online submissions for Search in Rotated Sorted Array.
Memory Usage: 42.1 MB, less than 75.19% of Java online submissions for Search in Rotated Sorted Array.
class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0, end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] > nums[start]) {
// [start, mid] is sorted
if (nums[start] <= target && nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
// [mid, end] is sorted
if (nums[mid] < target && nums[end] >= target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
if (nums[start] == target) {
return start;
}
return nums[end] == target ? end : -1;
}
}
三刷
Runtime: 1 ms, faster than 61.17% of Java online submissions for Search in Rotated Sorted Array.
Memory Usage: 42.7 MB, less than 44.35% of Java online submissions for Search in Rotated Sorted Array.
class Solution {
public int search(int[] nums, int target) {
if (nums == null) {
return -1;
}
int start = 0, end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[start] < nums[mid]) {
if (nums[start] <= target && nums[mid] >= target) {
end = mid;
} else {
start = mid + 1;
}
} else {
if (nums[mid] <= target && nums[end] >= target) {
start = mid;
} else {
end = mid - 1;
}
}
}
if (nums[start] == target) {
return start;
}
if (nums[end] == target) {
return end;
}
return -1;
}
}
94.70 %
class Solution {
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return -1;
}
int start = 0;
int end = nums.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[start] <= nums[mid]) { // [start, mid] is sorted
if (nums[mid] > target && nums[start] <= target) {
end = mid - 1;
} else {
start = mid + 1;
}
} else { // [mid, end] is sorted
if (nums[mid] < target && nums[end] >= target) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return nums[start] == target ? start : -1;
}
}
一刷
BST
先判断哪一边是有序，然后看target是否在有序的side
87.02 %
class Solution {
/* start -- mid -- end
0. target == mid return true
1. [start, mid] fully sorted
a. target is in this range -> end = mid - 1
b. target is not in this range -> start = mid + 1
2. [mid, end] fully sorted
a. target is in this range -> start = mid + 1
b. target is not in this range -> end = mid -1
*/
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) return -1;
int start = 0, end = nums.length - 1;
// exit when start == end
while (start < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) return mid;
// first half is fully ordered
if (nums[start] <= nums[mid]) {
if (nums[start] <= target && nums[mid] > target) end = mid - 1;
else start = mid + 1;
// second half is fully ordered
} else {
if (nums[mid] < target && nums[end] >= target) start = mid + 1;
else end = mid - 1;
}
}
return nums[start] == target ? start : -1;
}
}
No comments:
Post a Comment