Google : Find the number of duplicated number in sorted array

Given a sorted array and a number n.How can u find the
number of occurance of n in the array . should be o(logn)

简单题.

两次二分找上下界

两次二分找上下界
darksteel 发表于 2011-7-29 13:47

正确

1. 
   
2. int FindSide(int a[], int n, int num, bool bLeft)
   
3. {
   
4.         assert(a && n > 0);
   
5. 
   
6.         int nBeg = 0;
   
7.         int nEnd = n-1;
   
8.         int nPos = -1;
   
9. 
   
10.         while (nBeg <= nEnd)
    
11.         {
    
12.                 int nMid = (nBeg + nEnd)/2;
    
13.                 if (a[nMid] == num)
    
14.                 {
    
15.                         nPos = nMid;
    
16.                         if (bLeft)
    
17.                                 nEnd = nMid - 1;
    
18.                         else
    
19.                                 nBeg = nMid + 1;
    
20.                 }
    
21.                 else if (a[nMid] < num)
    
22.                         nBeg = nMid + 1;
    
23.                 else
    
24.                         nEnd = nMid - 1;
    
25.         }
    
26. 
    
27.         return nPos;
    
28. }
    
29. 
    
30. int GetNum(int a[], int n, int num)
    
31. {
    
32.         assert(a && n > 0);
    
33. 
    
34.         int l = FindSide(a, n, num, true);
    
35.         if (l < 0) return 0;
    
36. 
    
37.         int r = FindSide(a, n, num, false);
    
38. 
    
39.         return r - l + 1;
    
40. }
    

复制代码

是不是一次二分也行呢？

1. int getCount(int A[], int nLeft, nRight, int n)
   
2. {
   
3.          if (nLeft == nRight)
   
4.                  return A[nLeft] == n ? 1 : 0;
   
5. 
   
6.          int nMid = (nLeft + nRight) /2;
   
7.          if (A[nMid] == n)
   
8.            return getCount(A, nLeft, nMid - 1,n) + getCount(A, nMid + 1, nRight,n) + 1;
   
9.          else if (A[nMid] > n)
   
10.                  return getCount(A, nLeft, nMid -1, n );
    
11.          else
    
12.                  return getCount(A, nMid+1, nRight,n);
    
13. }
    

复制代码

Yunia 发表于 2012-7-16 14:06
是不是一次二分也行呢？

你这个不能算作“一次二分”。 因为你的递归树里可能有二叉 （第8行）。  他们的代码每一次递归都是严格一插到底LogN。