一、题目描述
统计一个数字在排序数组中出现的次数。
示例 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 <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
class Solution { public int search(int[] nums, int target) { } }
二、思路讲解
1、方法一
暴力查找。
2、方法二
二分查找改进。题目中的数组是已经排好序的，故而可以想到二分查找。
并且，在二分查找的基础上仍可以优化：当左边的数字小于target时，不可能找到了，可以直接break；同理，右边的数字大于target时，也可以直接break。
三、算法描述
1、方法一
遍历数组nums，若与target相等，则计数加一。
2、方法二
使用二分查找，若与target相等，则计数加一；一旦左边的指针指向的数小于target、右边的指针指向的数大于target时，可以提前结束。
四、Java代码实现
1、方法一
class Solution { public int search(int[] nums, int target) { int count = 0; for(int i=0; i<nums.length; i++) { if(target == nums[i]) { count++; } } return count; } }
2、方法二
if (nums.length == 0) { return 0; } int sum = 0; int mid = nums.length >> 2; if (nums[mid] == target) { sum++; } int i = mid, j = mid; while (i > 0 || j < nums.length - 1) { if (i > 0) { if (nums[i] >= target) { i--; if (nums[i] == target) { sum++; } } else { i = -1; } } if (j < nums.length - 1) { if (nums[j] <= target) { j++; if (nums[j] == target) { sum++; } } else { j = nums.length; } } } return sum;
五、时空复杂度分析
1、方法一
时间复杂度：O(n) 遍历数组nums
空间复杂度：O(1)
2、方法二
时间复杂度：O(logn) 二分查找的时间复杂度为logn
空间复杂度：O(1)
