微软面试题：在排序数组中，找出给定数字的出现次数,比如 [1, 2, 2,2, 3] 中2的出现次数是3次
思路1：最笨拙的方法，从头开始挨个判断是否是要寻找的数字
思路2：采用二分查找方法（先二分法找到最先出现的位置，然后从最先出现位置到最后再次二分查找找到最后出现的位置）。当然找最末位置的时候也可以不用二分，直接从第一次出现位置之后一个一个判断。个人认为在数组数据量非常大的时候还是用两次二分效率比较高
思路3：采用STL中的equal_range函数
思路4：有人说用hashtable,笔者笨拙，未通，希望大家指导！
下面是我根据以上思路的编程实现，望大家批评指导。
思路1
#include <iostream>
using namespace std;
int occurNum(int sortedArray[], int number)
{
int counter = 0;
int *p = sortedArray;
while(p!= NULL && *p <= number)
{
if(*p != number)
p++;
else
{
p++;
counter++;
}
}
return counter;
}
int main()
{
int testArray[5] = {1,2,2,2,3};
int number;
cin>>number;
int time = 0;
time= occurNum(testArray,number);
cout<<number<<"出现的次数为："<<time<<endl;
system("pause");
}
思路2
#include<iostream>
using namespace std;
int occurNum(int sortedArray[], int number)
{
int counter = 0;//出现次数
//找出第一次出现的位置
int begin = 0;
int end = sizeof(sortedArray);
int low, high, mid;
while(begin < end)
{
mid = (begin + end)/2;
if(sortedArray[mid]< number)
begin =mid + 1;
else
end = mid;
}
low = begin;
if(sortedArray[low] != number)
return 0;
//找出最后一次出现的位置
begin = low;
end = sizeof(sortedArray);
while(begin < end)
{
mid = (begin + end + 1)/2;
if(sortedArray[mid] <= number)
begin = mid;
else
end = mid - 1;
}
high = end;
//求出数字出现次数
counter = high - low + 1;
return counter;
}
int main()
{
int testArray[] = {1,2,2,2,3};
int number;
cin>>number;
int time = 0;
time = occurNum(testArray,number);
cout<<number<<"出现的次数为："<<time<<endl;
system("pause");
}
思路3
#include<iostream>
#include <algorithm>
using namespace std;
int occurNum(int sortedArray[], int number)
{
int num = sizeof(sortedArray);
pair<int*,int*> p1;//数字出现的位置
int count = 0;//数字出现次数
p1 = equal_range(sortedArray,sortedArray+num,number);
count = p1.second - p1.first;
return count;
}
int main()
{
int testArray[5] = {1,2,2,2,3};
int number;//要查找的数字
cin>>number;
int time = occurNum(testArray,number);
cout<<number<<"出现的次数为："<<time<<endl;
system("pause");
}