题目描述
统计一个数字在排序数组中出现的次数。
思路：
已知是排序数组，利用二分查找到k的上下界，相减
class Solution
{
public:
int GetNumberOfK(vector<
int> data,
int k)
{
if (data.empty())
return 0;
int low = getLowerK(data,
0, data.size() -
1, k);
int high = getHigherK(data,
0, data.size() -
1, k);
cout << low <<
" " << high <<
endl;
if (low > -
1 && high > -
1)
return (high - low +
1);
return 0;
}
int getLowerK(vector<
int> &data,
int beg,
int end,
int k)
{
if (beg >
end)
return -
1;
int mid = beg + (end - beg) /
2;
if (data[mid] ==
k)
{
if ((mid == beg) || (data[mid -
1] !=
k))
return mid;
else
end = mid -
1;
}
else if (data[mid] >
k)
end = mid -
1;
else
beg = mid +
1;
return getLowerK(data, beg, end, k);
}
int getHigherK(vector<
int> &data,
int beg,
int end,
int k)
{
if (beg >
end)
return -
1;
int mid = beg + (end - beg) /
2;
if (data[mid] ==
k)
{
if ((mid == end) || (data[mid +
1] !=
k))
return mid;
else
beg = mid +
1;
}
else if (data[mid] >
k)
end = mid -
1;
else
beg = mid +
1;
return getHigherK(data, beg, end, k);
}
};
转载于:https://www.cnblogs.com/ruoh3kou/p/10147131.html
