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

今天药忘吃喽~ 2022-03-20 03:27 179阅读 0赞

**何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ**

**题目描述：[http://ac.jobdu.com/problem.php?cid=1039&pid=20][http_ac.jobdu.com_problem.php_cid_1039_pid_20]**

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

**输入：**

每个测试案例包括两行：

第一行有1个整数n，表示数组的大小。1<=n <= 10^6。

第二行有n个整数，表示数组元素，每个元素均为int。

第三行有1个整数m，表示接下来有m次查询。1<=m<=10^3。

下面有m行，每行有一个整数k，表示要查询的数。

**输出：**

对应每个测试案例，有m行输出，每行1整数，表示数组中该数字出现的次数。

**样例输入：**

1 2 3 3 3 3 4 5

**样例输出：**

**           4**

**思想：使用二分法找到具体数字的位置，然后需要前后扫描来确定数字的个数~^\_^**

**代码AC：**

// 用2分法！！ ^_^
    
    #include <stdio.h>
    #include <stdlib.h>
    
    int main()
    {
        long int n, i, cou, mid, low, high;
        int  m, *num, k;
        
        while( scanf( "%ld", &n ) != EOF )
        {
               num = ( int* )malloc( sizeof( int ) * n );
               
               for( i = 0; i < n; i++ )
               {
                    scanf("%d", &num[i]);
               }
               
               scanf("%d", &m);
               
               while( m-- )
               {
                      scanf("%d", &k);
                      
                      low = 0;
                      high = n - 1;
                      while( low <= high )
                      {
                             mid = ( low + high ) / 2;
                             if( k == num[mid] )
                             {
                                 break;
                             }
                             else if( k > num[mid] )
                             {
                                  low = mid + 1;
                             }
                             else
                             {
                                 high = mid - 1;
                             }
                      }
                      
                      cou = 0;
                      i = mid;
                      while( i < n )
                      {
                             if( num[i] == k )
                             {
                                 cou++;
                                 i++;
                             }
                             else
                             {
                                 break;
                             }
                      }
                      
                      i = mid - 1;
                      while( i >= 0 )
                      {
                             if( num[i] == k )
                             {
                                 cou++;
                                 i--;
                             }
                             else
                             {
                                 break;
                             }
                      }
                      
                      printf("%d\n", cou);
               }
        }
        
        return 0;
    }

** **

[http_ac.jobdu.com_problem.php_cid_1039_pid_20]: http://ac.jobdu.com/problem.php?cid=1039&pid=20