数字在排序数组中出现的次数
发布时间:2020-12-14 04:48:48 所属栏目:大数据 来源:网络整理
导读:题目描述 统计一个数字在排序数组中出现的次数。 思路:排序数组即排好序的数组,对于排好序的数组,我们就会想到二分法, 本题就是用二分法查找到值,则返回下标,再在此值左右两边计数查找。 代码: int BinarySearch(vector int data, int low, int high,
题目描述
统计一个数字在排序数组中出现的次数。
思路:排序数组即排好序的数组,对于排好序的数组,我们就会想到二分法,
本题就是用二分法查找到值,则返回下标,再在此值左右两边计数查找。
代码:
int BinarySearch(vector<int> data,int low,int high,int k) { while(low <= high) { int m = low + (high-low)/2; if(data[m] == k) return m; else if(data[m] > k) high = m-1; else low = m+1; } return -1; } int GetNumberOfK(vector<int> data,int k) { int len = data.size(); int index ; index = BinarySearch(data,0,len-1,k); if(index == -1) return 0; int low = index-1; int n1 = 0; int n2 = 0; int high = index+1; while((low >= 0) && (data[low] == k)) { low--; n1++; } while((high<len) && (data[high] == k)) { high++; n2++; } return n1+n2+1; } 看到的特别的想法: 思路:例如:样例 1,2,4,5,6? ?查找4的个数,则把3.5和4.5插入,1,3.5,4.5,6? 则4.5的位置减去3.5的位置就是4的个数。 但是这种方法在元素少的时候不如上一个方法的时间复杂度。因为要调用两次二分。 int GetNumberOfK(vector<int> data,int k) { return biSearch(data,k+0.5) - biSearch(data,k-0.5) ; } int biSearch(const vector<int> & data,double num){ int s = 0,e = data.size()-1; while(s <= e){ int mid = (e - s)/2 + s; if(data[mid] < num) s = mid + 1; else if(data[mid] > num) e = mid - 1; } return s; } 两个方法的比较:
?复杂度差不多,但是第一种方法最坏复杂度更高,最好复杂度更低,不够稳定。
双二分的比较稳定,但是元素少的时候效率不如第一种?。
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |