My code:
public class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums == null || nums.length == 0)
return null;
int[] ret = new int[2];
int begin = 0;
int end = nums.length - 1;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
if (nums[mid] > target)
end = mid - 1;
else if (nums[mid] < target)
begin = mid + 1;
else {
int pre = mid;
while (pre >= 0 && nums[pre] == nums[mid])
pre--;
int post = mid;
while (post < nums.length && nums[post] == nums[mid])
post++;
ret[0] = pre + 1;
ret[1] = post - 1;
return ret;
}
}
ret[0] = -1;
ret[1] = -1;
return ret;
}
}
这道题目还是挺简单的。
就是一个简单的binary search。
**
总结： binary search
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ret = new int[2];
ret[0] = -1;
ret[1] = -1;
if (nums == null || nums.length == 0)
return ret;
int begin = 0;
int end = nums.length - 1;
while (begin <= end) {
int middle = begin + (end - begin) / 2;
if (nums[middle] > target) {
int i = middle - 1;
while (i >= 0 && nums[i] == nums[i + 1])
i--;
if (i < 0)
break;
else
end = i;
}
else if (nums[middle] < target) {
int i = middle + 1;
while (i <= nums.length - 1 && nums[i] == nums[i - 1])
i++;
if (i > nums.length - 1)
break;
else
begin = i;
}
else {
int left = middle - 1;
while (left >= 0 && nums[left] == nums[left + 1])
left--;
ret[0] = left + 1;
int right = middle + 1;
while (right <= nums.length - 1 && nums[right] == nums[right - 1])
right++;
ret[1] = right - 1;
return ret;
}
}
ret[0] = -1;
ret[0] = -1;
return ret;
}
}
一道简单的binary search题目。和以前的代码相比，我这次复杂了一些。为什么呢。因为在 > <的情况下，我仍然采用了滑动，所以速度应该更快些。
Anyway, Good luck, Richardo!
