当前位置 博文首页 > Liu，：Leetcode——在排序数组中查找数字 I（二分查找）
统计一个数字在排序数组中出现的次数。
class Solution {
public int search(int[] nums, int target) {
int count = 0;
if(nums == null || nums.length == 0)
return 0;
int len= nums.length - 1;
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i <= len; i++){
map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
}
if(map.containsKey(target))
return map.get(target);
return 0;
}
}
暴力枚举:
class Solution {
public int search(int[] nums, int target) {
int count = 0;
if(nums == null || nums.length == 0)
return 0;
int len= nums.length - 1;
for(int i = 0; i <= len; i++){
if(nums[i] == target)
count++;
}
return count;
}
}
二分法+线性搜索：
// 找到目标值「最后」出现的分割点，并「往前」进行统计
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
//区间为[0,n) 左闭右开
//寻找右边界
int left = 0, right = n;
while (left < right) {
int mid = left + (right - left) / 2 ;
if(nums[mid] == target)
left = mid + 1;
//区间为[0,n) 左闭右开：nums[mid] == target，下一个值为mid + 1
//[0,mid)，不包括mid
else if(nums[mid] < target)
left = mid + 1;
else if(nums[mid] > target)
right = mid;
}
right = left - 1;
int ans = 0;
while(right >= 0 && nums[right] == target ){ //判断right > 0 即可
right--;
ans++;
}
return ans;
}
}
二分法+线性搜索：
// 找到目标值「开始」出现的分割点，并「往后」进行统计
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
//寻找左边界
int left = 0, right = n;
while (left < right) {
int mid = left + (right - left) / 2 ;
if(nums[mid] == target)
right = mid;
//区间为[0,n) 左闭右开：nums[mid] == target，下一个值为mid，[0，mid）
else if(nums[mid] < target)
left = mid + 1;
else if(nums[mid] > target)
right = mid;
}
int ans = 0;
while(left < n && nums[left] == target ){
//（nums[left] == target && left < n） 就会报错
//必须先判断left < n，防止数组越界
left++;
ans++;
}
return ans;
}
}
// 两次二分 分别找到左右边界
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int a = -1, b = -1; //分别存储左右边界
//寻找左边界
int left = 0, right = n;
while (left < right) {
int mid = left + (right - left) / 2 ;
if(nums[mid] == target)
right = mid;
else if(nums[mid] < target)
left = mid + 1;
else if(nums[mid] > target)
right = mid;
}
a = left;
//寻找右边界
left = 0;
right = n;
while (left < right) {
int mid = left + (right - left) / 2 ;
if(nums[mid] == target)
left = mid + 1;
else if(nums[mid] < target)
left = mid + 1;
else if(nums[mid] > target)
right = mid;
}
b = left - 1;
//计算结果
int ans = b - a + 1;
return ans;
}
}
