做的网站在ie会乱码,成都住建局官网住建蓉e办,免费企业建站cms,常州做的网站的公司网站题目描写叙述 统计一个数字在排序数组中出现的次数。解题思路 数组是排序的#xff0c;所以反复出现的数字是相邻排列的。 用二分查找算法#xff0c;找到第一次出现的位置。和 最后一次出现的位置。 推断第一次出现的位置条件为#xff1a;当前数字的前一个是否与之相等。若… 题目描写叙述 统计一个数字在排序数组中出现的次数。 解题思路 数组是排序的所以反复出现的数字是相邻排列的。 用二分查找算法找到第一次出现的位置。和 最后一次出现的位置。 推断第一次出现的位置条件为当前数字的前一个是否与之相等。若是则继续查找否则该位置就是第一次出现的位置。 推断最后一次出现的位置条件为当前数字的后一个是否与之相等若是则继续查找否则该位置就是最后一次出现的位置。 出现的次数 last - first 1 时间复杂度O(logn) 实现代码 class Solution {
public:int GetNumberOfK(vectorint data ,int k) {int result0;if(data.empty())return 0;int start 0;int end data.size()-1;int first getFirstK(data,k,start,end);int last getLastK(data,k,start,end);if(first -1 last -1)result last - first1;return result;}int getFirstK(vectorint data, int k, int start, int end){if(start end)return -1;int midIndex (start end)/2;int midData data[midIndex];if(midData k){if(midIndex 0 data[midIndex-1] ! k || midIndex 0)return midIndex;elseend midIndex-1;}else if(midData k)end midIndex-1;elsestart midIndex1;return getFirstK(data,k,start,end);}int getLastK(vectorint data, int k, int start, int end){if(start end)return -1;int midIndex (start end)/2;int midData data[midIndex];if(midData k){if(midIndex data.size()-1 data[midIndex1] ! k || midIndex data.size()-1)return midIndex;elsestart midIndex1;}else if(midData k)end midIndex-1;elsestart midIndex1;return getLastK(data,k,start,end);}
}; 转载于:https://www.cnblogs.com/yangykaifa/p/6748762.html
