Description

面试题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
限制：
0 <= 数组长度 <= 50000

Solution

利用二分查找的变种，查找第一个等于给定值的元素。

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         int lo = 0, hi = nums.length-1, mid=0;
  4.         while(lo <= hi){
  5.             mid = lo + (hi - lo) / 2;
  7.             if(nums[mid] > target){
  8.                 hi = mid - 1;
  9.             }else if (nums[mid] < target){
  10.                 lo = mid + 1;
  11.             }else{   
  12.                 if(mid == 0 || nums[mid - 1] != target)
  13.                     break;
  14.                 else    
  15.                     hi = mid - 1;
  16.             }
  17.         }
  18.         int res = 0;
  19.         while(mid < nums.length && nums[mid++] == target)
  20.             res ++;
  21.         return res;
  22.     }
  23. }

执行结果
执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗 :43 MB, 在所有 Java 提交中击败了100.00%的用户