剣指offer面接問題38:数字がソート配列に現れる回数

タイトルの説明:
ソート配列に表示される数値の回数を統計します.
入力:
各テストケースには、次の2つの行があります.
最初の行には1つの整数nがあり、配列の大きさを表す.1<=n <= 10^6.
2行目にはn個の整数があり、配列要素を表し、各要素はintである.
3行目には1つの整数mがあり、次にm回のクエリがあることを示します.1<=m<=10^3.
以下にm行があり、各行に整数kがあり、クエリーする数を表す.
出力:
各テストケースに対応して、m行出力があり、各行1整数で、配列内のこの数字が現れる回数を表す.
サンプル入力:

81 2 3 3 3 3 4 513

サンプル出力:

4

テーマ分析:
数値がソート配列に現れる回数は,hash法を用いて配列中のすべてのデータが現れる回数を計算し,その後直接検索し,時間複雑度O(n),空間複雑度O(n)であるべきである.しかし,この方法ではこの配列を利用できなかったのがソートの特徴であるため,ソートに関する問題は,直ちに二分検索を連想しなければならない.
この問題は,二分検索の変形を用いて,検索する数が配列中に最初に出現する位置と最後に出現する位置を求め,配列中に数値が出現する回数を決定することである.
もちろん、具体的なプログラムを書く過程では、いくつかの臨界条件の判断と特殊な状況の処理にも注意しなければならない(ある数が現れる位置が0である場合と、配列の中でこの数字が0に戻っていない場合とを区別し、私のプログラムではマークでこの2つの状況を区別した).二分探索時間複雑度はO(logn)であり,時間複雑度を低減した.

//source:http://ac.jobdu.com/problem.php?pid=1349
#include <iostream>
#include <cstdio>
using namespace std;

bool flag1 = true;
bool flag2 = true;
int SearchFirst(int A[], int n, int value)
{
	int left = 0, right = n - 1;
	while (left <= right)
	{
		int mid = (left + right)/2;
		if (A[mid] < value)
			left = mid + 1;
		else if (A[mid] > value)
			right = mid - 1;
		else
		{
			if (A[mid - 1] != value || mid == 0)//mid==0
				return mid;
			else
				right = mid - 1;
		}
	}
	flag1 = false;
	return 0;
}

int SearchLast(int A[],int n, int value)
{
	int left = 0, right = n - 1;
	while (left <= right)
	{
		int mid = (left + right)/2;
		if (A[mid] < value)
			left = mid + 1;
		else if (A[mid] > value)
			right = mid - 1;
		else
		{
			if (A[mid + 1] != value || mid == n)//mid==n
				return mid;
			else
				left = mid + 1;
		}
	}
	flag2 = false;
	return 0;
}

int main()
{
	int n, m;//n ，m 
	int k;// 
	while (scanf("%d",&n)!=EOF)
	{
		int *array = new int[n+1];
		for (int i = 0; i < n; i++)
		{
			scanf("%d", array+i);
		}

		scanf ("%d",&m);
		while (m--)
		{
			scanf("%d",&k);
			int first =SearchFirst(array,n,k);
			int last = SearchLast(array,n,k);
			if (!flag1 && !flag2)
				printf("0
");
			else
				printf("%d
",last - first + 1);
		}
	}
	return 0;
}