面试题53 - I. 在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
简单暴力解法
class Solution { public int search(int[] nums, int target) { int sum=0; for(int i=0;i<nums.length;i++){ if(nums[i]==target){ sum++; } } return sum; } }
二分查找
因为数组是已经排序好的数组,所以可以先找出左右边界,找到数组中的左右边界,然后相减就可以拿到这个数字了.
/** * @Auther: truedei * @Date: 2020 /20-5-20 08:45 * @Description: */ public class Test1 { static public int search(int[] nums, int target) { int i=0; int j=nums.length-1; int left=0,right=0; //搜索左边界 while (i<=j){ int mid = (i + j) /2; if(nums[mid] <= target) i = i + 1; else j = j - 1; } right = i; i = 0; j=nums.length-1; //搜索右边界 while (i<=j){ int mid = (i + j) /2; if(nums[mid] < target) i = i + 1; else j = j - 1; } left=j; return right - left - 1; } public static void main(String[] args) { int nums[] = new int[]{5,7,7,8,8,10},target = 8; System.out.println(search(nums,target)); } }
