AlgoPressAppearance
53-I-在排序数组中查找数字I
题目描述
https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
提示： $$ 0 <= nums.length <= 10^5 \ -10^9 <= nums[i] <= 10^9 \ nums 是一个非递减数组 \ -10^9 <= target <= 10^9 $$
注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
来源：力扣（LeetCode） 链接： 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1 常规搜索，时间复杂度n
实现代码
csharp
public class Solution {
public int Search(int[] nums, int target) {
int count = 0;
for(int i = 0; i < nums.Length; i++){
if(nums[i] == target){
count++;
}
else{
if(count > 0){
return count;
}
}
}
return count;
}
}
思路2： 二分法
本地用常规解法肯定不是面试官期望的解，因为已经排序好的数组，所以应该可以使用二分法
csharp
public class Solution {
public int Search(int[] nums, int target) {
if(nums.Length == 0){
return 0;
}
int index = BinarySearch(nums,0,nums.Length-1,target);
//两边延伸
if(index == -1){
return 0;
}
int count = 1;
for(int i=index-1; i>=0; i--){
if(nums[i] == target){
count++;
}
else{
break;
}
}
for(int i=index+1; i<nums.Length; i++){
if(nums[i] == target){
count++;
}
else{
break;
}
}
return count;
}
//找出 index
private int BinarySearch(int[] nums, int left, int right, int target){
if(left == right){
if(nums[left] != target){
return -1;
}
}
int mid = left + (right - left) / 2;
if(nums[mid] == target){
return mid;
}
else if(nums[mid] < target){
return BinarySearch(nums, mid+1, right, target);
}
else{
return BinarySearch(nums, left, mid, target);
}
}
}