剑指Offer_#53 - I_在排序数组中查找数字
Contents
题目
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0限制：
0 <= 数组长度 <= 50000思路分析
因为是有序数组，所以想到使用二分查找。某一个数字在有序数组中会出现多次，所以需要分别确定重复数字所在范围的左右边界。
这里的左右边界是不在重复数字范围内的，而是在重复数字范围的向左或向右一个数字的位置。在二分查找时，不是用mid来定位。
- 左边界是使用右指针
j定位，因为最后一次循环开始时应该满足i==j==mid，之后执行j = m - 1,此时跳出循环，j刚好是重复数字范围左边第一个数字的下标。 - 右边界同理，不同的是当
nums[mid] == target时，应该右移左指针i。
解答1：循环
class Solution {
public int search(int[] nums, int target) {
//前后双指针，用于不断缩小范围
int i = 0;
int j = nums.length - 1;
//搜索左边界
while(i <= j){
int m = (i + j) / 2;
if(nums[m] > target) j = m - 1;
if(nums[m] < target) i = m + 1;
if(nums[m] == target) j = m - 1;
}
int left = j;
//如果数组里没有target，直接返回0
if(i > 0 && i <nums.length && nums[i] != target) return 0;
//搜索右边界
i = 0;
j = nums.length - 1;
while(i <= j){
int m = (i + j) / 2;
if(nums[m] > target) j = m - 1;
if(nums[m] < target) i = m + 1;
//只有等于的情况不同
if(nums[m] == target) i = m + 1;
}
int right = i;
return right - left - 1;
}
}感觉这个代码并没有处理到只有一个元素的情况，虽然最后结果是对的，但是感觉好像是因为巧合正好对了，所以不是很推荐这种写法吧。
解答2:剑指Offer写法
这是书中的解法，感觉逻辑非常清晰，所有的情况都被“显式”的考虑到了，面试尽量用这个方法。
递归版本：
class Solution {
public int search(int[] nums, int target) {
int first = getFirstTarget(nums, target, 0, nums.length - 1);
int last = getLastTarget(nums, target, 0, nums.length - 1);
if(first != -1 && last != -1) return last - first + 1;
else return 0;
}
private int getFirstTarget(int[] nums, int target, int start, int end){
if(start > end) return -1;
int mid = (start + end);
if(nums[mid] == target){
if((mid >= 1 && nums[mid - 1] != target) || mid == 0){
return mid;
}else{
end = mid - 1;
}
}else if(nums[mid] > target){
end = mid - 1;
}else{
start = mid + 1;
}
return getFirstTarget(nums, target, start, end);
}
private int getLastTarget(int[] nums, int target, int start, int end){
if(start > end) return -1;
int mid = (start + end);
if(nums[mid] == target){
if((mid < nums.length - 1 && nums[mid + 1] != target) || mid == nums.length - 1){
return mid;
}else{
end = mid + 1;
}
}else if(nums[mid] > target){
end = mid - 1;
}else{
start = mid + 1;
}
return getLastTarget(nums, target, start, end);
}
}循环版本
class Solution {
public int search(int[] nums, int target) {
int first = getFirstTarget(nums, target, 0, nums.length - 1);
int last = getLastTarget(nums, target, 0, nums.length - 1);
if (first != -1 && last != -1) return last - first + 1;
else return 0;
}
private int getFirstTarget(int[] nums, int target, int start, int end) {
while (start <= end) {
int mid = (start + end);
if (nums[mid] == target) {
if ((mid >= 1 && nums[mid - 1] != target) || mid == 0) {
return mid;
} else {
end = mid - 1;
}
} else if (nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
private int getLastTarget(int[] nums, int target, int start, int end) {
while (start <= end) {
int mid = (start + end);
if (nums[mid] == target) {
if ((mid < nums.length - 1 && nums[mid + 1] != target) || mid == nums.length - 1) {
return mid;
} else {
end = mid + 1;
}
} else if (nums[mid] > target) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
}