37数字在排序数组中出现的次数

题目描述

统计一个数字在排序数组中出现的次数

思路1：暴力循环 O（N）

public class Solution {
    public int GetNumberOfK(int [] a, int k) {
        int cnt=0;
       for(int i=0;i<a.length;i++)
           if(a[i]==k)
               cnt++;
        return cnt;
    }
}

思路2：利用二分查找 O(logN)

利用二分查找找到所求数字第一次出现的位置与最后出现的位置。
2个位置差就是次数。

利用2分查找找到第一个k（所求的数），拿K与数组中间的数字相比，如果K大，则去后半部分找；
如果K小，则去前半部分找，如果相等，判断当前的K是不是第一次出现。（如果K等于K前面的数字，则不是第一次出现，如果K大于K前面的数字，则是第一次出现)，如果K不是第一次出现，则去K前面继续找，如果是第一次出现，则找到了位置。

 1 public class Solution {
 2         public int GetNumberOfK(int [] a, int k) {
 3             if(a.length==0) return 0;
 4             int f = GetFirstK(a, k);
 5             int l = GetLstK(a,k);
 6             if(a[f]==k && a[l]==k)
 7                 return  l-f+1;
 8             else
 9                 return 0;
10         }
11     
12         private int GetFirstK(int a[],int k) {
13             
14             int lo = 0,hi=a.length-1;
15             int mid  =0;
16             while(true) {
17                 if(lo>=hi) return hi;
18                   mid  = (hi-lo)/2+lo;
19                  if(k<a[mid])
20                      hi=mid-1;
21                  else if(k>a[mid]){
22                      lo=mid+1;
23                 }
24                  else {
25                     if(mid-1>=lo&&a[mid-1]==k)
26                         hi = mid-1;
27                     else
28                         return mid;                    
29                 }
30             }       
31         }
32     private int GetLstK(int a[],int k) {
33             
34             int lo = 0,hi=a.length-1;
35             int mid = 0;
36             while(true) {
37                 if(lo>=hi) return lo;
38                  mid  = (hi-lo)/2+lo;
39                  if(k<a[mid])
40                      hi=mid-1;
41                  else if(k>a[mid]){
42                      lo=mid+1;
43                 }
44                  else {
45                     if(mid+1<=hi&&a[mid+1]==k)
46                         lo = mid+1;
47                     else
48                         return mid;    
49                 }
50             }    
51         }
52     
53     
54     
55 }

20180311

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3 
 4     def GetNumberOfK(self, data, k):
 5         # write code here
 6         def fun_f(a, target):
 7             lo = 0
 8             hi = len(a) - 1
 9 
10             while(lo <= hi):
11                 mid = lo + int((hi - lo) / 2)
12                 if(target <= a[mid]):
13                     hi = mid - 1
14                 else:
15                     lo = mid + 1
16             return lo
17 
18         def fun_l(a, target):
19             lo = 0
20             hi = len(a) - 1
21 
22             while(lo <= hi):
23                 mid = lo + int((hi - lo) / 2)
24                 if(target < a[mid]):
25                     hi = mid - 1
26                 else:
27                     lo = mid + 1
28             return lo
29         return fun_l(data, k) - fun_f(data, k)