三刷
Runtime: 1 ms, faster than 80.32% of Java online submissions for Search in Rotated Sorted Array II.
Memory Usage: 43.6 MB, less than 64.65% of Java online submissions for Search in Rotated Sorted Array II.
class Solution {
public boolean search(int[] nums, int target) {
if (nums == null) {
return false;
}
int start = 0, end = nums.length - 1;
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[mid] == nums[start]) {
start++;
} else if (nums[mid] == nums[end]) {
end--;
} else if (nums[mid] > nums[start]) {
if (nums[start] <= target && target < nums[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[end]) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
if (nums[start] == target || nums[end] == target) {
return true;
}
return false;
}
}
The only difference is that due to the existence of duplicates, we can have nums[left] == nums[mid] and in that case, the first half could be out of order (i.e. NOT in the ascending order, e.g. [3 1 2 3 3 3 3]) and we have to deal this case separately. In that case, it is guaranteed that nums[right] also equals to nums[mid], so what we can do is to check if nums[mid]== nums[left] == nums[right] before the original logic, and if so, we can move left and right both towards the middle by 1. and repeat.
29.43 %
class Solution {
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return false;
}
int start = 0;
int end = nums.length - 1;
while (start < end) {
int mid = start + (end - start) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[start] == nums[mid] && nums[mid] == nums[end]) {
start++;
end--;
} else if (nums[start] <= nums[mid]) { // [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;
}
}
}
return nums[start] == target;
}
}
一刷
Submission Result: Wrong Answer More Details
3 1 2 3 3 3 3
3 3 3 3 1 2 3
一开始以为duplicates不会有影响，后来发现too young too simple了
上面是两个反例
所以用< 和 > 判断出fully ordered之后， 还存在start == mid || end == mid 的情况
这种情况下只能排除start和end，所以start++ || end--
Time worst case O(n) General case O(logn)
12.55 %
class Solution {
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) return false;
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 true;
// 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[end] > nums[mid]) {
if (nums[mid] < target && nums[end] >= target) start = mid + 1;
else end = mid - 1;
} else {
if (nums[start] == nums[mid]) start++;
if (nums[end] == nums[mid]) end--;
}
}
return nums[start] == target;
}
}
No comments:
Post a Comment