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

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

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

题目描述：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

样例输出：

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

代码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;
}

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

相关推荐