首页 > 其他 > 详细

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

时间:2014-08-17 18:36:12      阅读:389      评论:0      收藏:0      [点我收藏+]
题目描述:
统计一个数字在排序数组中出现的次数。
输入:

每个测试案例包括两行:

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

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

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

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

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

样例输入:
81 2 3 3 3 3 4 513
样例输出:
4
思路:
题目说的是排序数组,所以我们很自然的想到二分查找。
解法1:首先通过二分查找找到该数字,然后以该数字的位置为起点,分别向左向右依次遍历,找到所有相同的数字,求和即可。

代码:

/*
数字在排序数组中出现的次数
by Rowandjj
2014/8/17
*/
#include<stdio.h>
#include<stdlib.h>
int GetTimes(int arr[],int len,int target)
{
	if(arr == NULL || len <= 0)
	{
		return 0;
	}
	int low = 0,high = len-1;
	while(low <= high)
	{
		int mid = low + ((high-low)>>1);
		if(arr[mid] == target)
		{
			int count = 1;
			int i;
			for(i = mid-1;i >= 0; i--)
			{
				if(arr[i] != target)
				{
					break;
				}
				count++;
			}
			for(i = mid+1; i <= len; i++)
			{
				if(arr[i] != target)
				{
					break;
				}
				count++;
			}
			return count;
		}else if(arr[mid] > target)
		{
			high = mid-1;
		}else
		{
			low = mid+1;
		}
	}
	return 0;
}
int main()
{
	int n;  
    while(scanf("%d",&n) != EOF)  
    {  
        int *arr = (int *)malloc(n*sizeof(int));  
        if(arr == NULL)  
            exit(EXIT_FAILURE);  
		
        int i;  
        for(i=0;i<n;i++)  
            scanf("%d",arr+i);  
        int m;  
        scanf("%d",&m);  
        for(i=0;i<m;i++)  
        {  
            int k;  
            scanf("%d",&k);  
            printf("%d\n",GetTimes(arr,n,k));  
        }  
		
        free(arr);  
        arr = NULL;  
    }  
    return 0;  
}

解法2:其实二分查找不光可以找到一个数字的位置,还可以找到第一次出现的位置和最后一次出现的位置,比如我们想求k第一次出现的位置,首先我们拿数组中间的数字和k作比较,如果中间的数字比k大,那么k只会出现在前半段,下一轮我们只在数组的前半段找即可,如果中间的数字比k小,那么k只可能出现在数组的后半段,下一轮我们只在数组的后半段找即可,如果中间的数字和k相等,我们首先判断这个数字是不是第一个k,如果位于中间数字的前面一个数字也是k,也就是说第一个k肯定在数组的前半段,下一轮我们仍然需要在数组的前半段查找,如果位于中间数字的前面一个数字不是k,那么说明当前k即第一次出现的位置。查找最后一次出现的位置和这个类似。
代码:
#include<stdio.h>
#include<stdlib.h>
int GetFirstN(int arr[],int len,int target)
{
	if(arr == NULL || len<=0)
	{
		return -1;
	}
	int low = 0,high = len-1;
	while(low <= high)
	{
		int mid = low + ((high-low)>>1);
		if(arr[mid] == target)
		{
			if(mid == 0 || arr[mid-1] != target)
			{
				return mid;
			}else
			{
				high = mid-1;
			}
		}else if(arr[mid] > target)
		{
			high = mid-1;
		}else
		{
			low = mid+1;
		}
	}
	return -1;
}
int GetLastN(int arr[],int len,int target)
{
	if(arr == NULL || len <= 0)
	{
		return -1;
	}
	int low = 0,high = len-1;
	while(low <= high)
	{
		int mid = low + ((high-low)>>1);
		if(arr[mid] == target)
		{
			if(mid == len-1 || arr[mid+1] != target)
			{		
				return mid;
			}else		
			{	
				low = mid+1;
			}
		}else if(arr[mid] > target)
		{
			high = mid-1;
		}else
		{
			low = mid+1;
		}
	}
	return -1;
}
int GetTimes(int arr[],int len,int target)
{
	if(arr == NULL || len <= 0)
	{
		return 0;
	}
	int t1 = GetFirstN(arr,len,target);
	int t2 = GetLastN(arr,len,target);
	if(t1 !=-1 && t2 != -1)
	{
		return t2-t1+1;		
	}else
	{
		return 0;
	}
}
int main()
{
	int n;  
    while(scanf("%d",&n) != EOF)  
    {  
        int *arr = (int *)malloc(n*sizeof(int));  
        if(arr == NULL)  
            exit(-1);  
        int i;  
        for(i=0;i<n;i++)  
            scanf("%d",arr+i);  
        int m;  
        scanf("%d",&m);  
        for(i=0;i<m;i++)  
        {  
            int k;  
            scanf("%d",&k);  
            printf("%d\n",GetTimes(arr,n,k));  
        }  
		
        free(arr);  
        arr = NULL;  
    }  
    return 0;  
}




数字在排序数组中出现的次数,布布扣,bubuko.com

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

原文:http://blog.csdn.net/chdjj/article/details/38640697

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!