在排序数组中,找出给定数字的出现次数,比如 [1, 2, 2, 2, 3] 中2的出现次数是3次。
----------------------------------------------------------------------
网上一位仁兄写了如下解法:
int cnt(int a[], int v, int n)
{
int mid, b = 0, e = n-1;
int low, high;
while(b < e - 1)
{
mid = b + (e-b)/2;
if(a[mid] >= v)
e = mid;
else
b = mid;
}
if(a[b] == v)
low = b;
else if(a[e] == v)
low = e;
else
return 0;
b = 0;
e = n-1;
while(b < e -1)
{
mid = b +(e-b)/2;
if(a[mid] <= v)
b = mid;
else
e = mid;
}
if (a[e] == v)
high = e;
else if(a[b] == v)
high = b;
else
return 0;
return high - low + 1;
}
个人认为可以先找到所指定的数,找到之后保留这个二分级数再向两端扩展可能会稍微快一点。
有几位仁兄说可以用hashtable来解决,但我感觉面试考的不是用hash
分享到:
相关推荐
面试题53 - I. 在排序数组中查找数字 I题目链接面试题53 - I. 在排序数组中查找数字 I题目描述统计一个数字在排序数组中出现的次数。题解public
java基础面试题数字在排序数组中出现的次数本资源系百度网盘分享地址
面试题56 - I. 数组中数字出现的次数题目链接面试题56 - I. 数组中数字出现的次数题目描述一个整型数组里除了两个数字之外,其他的数字都出现了两次。传出
难度:简单 一、题目描述: 二、解题分析: 1、剑指解析 2、代码实现 I、剑指思路 class Solution: def extreme_insertion_index(self, nums, target, left): ... while lo target or (left and target == nums[mid]...
剑指offer面试题66--构建乘积数组给定一个数组A[0, 1,...n - 1],请构建一个数组A[0, 1,...n - 1],其中B中的元素B[i] =
java面试题 java面试题_leetcode题解之第153题寻找排序数组中的最小值
java面试题 java面试题_leetcode题解之第34题在排序数组中查找元素的第一个和最后一个位置
数组 - 需要参加面试的人
微软面试题 资源源于不但搜索,自由源于不但努力
上海Linux运维工程师-面试题-个人总结).docx上海Linux运维工程师-面试题-个人总结).docx上海Linux运维工程师-面试题-个人总结).docx上海Linux运维工程师-面试题-个人总结).docx上海Linux运维工程师-面试题-个人总结)...
c语言面试题 c语言面试题之哈希表找到所有数组中消失的数字
最新22道面试题-Vue系列最新22道面试题-Vue系列最新22道面试题-Vue系列最新22道面试题-Vue系列最新22道面试题-Vue系列最新22道面试题-Vue系列最新22道面试题-Vue系列最新22道面试题-Vue系列最新22道面试题-Vue系列...
java面试题-50java面试题-50道最容易考的java题java面试题-50道最容易考的java题java面试题-50道最容易考的java题java面试题-50道最容易考的java题java面试题-50道最容易考的java题java面试题-50道最容易考的java题...
面试题 10.01. 合并排序的数组标签:数组、双指针、排序难度:简单题目大意给定两个排序后的数组 A 和 B,以及 A 的元素数量 m 和 B 的元素数量 n
上海Linux运维工程师-面试题-个人总结).pdf上海Linux运维工程师-面试题-个人总结).pdf上海Linux运维工程师-面试题-个人总结).pdf上海Linux运维工程师-面试题-个人总结).pdf上海Linux运维工程师-面试题-个人总结).pdf...
c语言面试题 c语言面试题之双指针按奇偶排序数组
请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。 解题思路参考:https://blog.csdn.net/flower_48237/article/details/104025402
最新各大公司企业真实面试题-Java面试题最新各大公司企业真实面试题-Java面试题
面试题 10.01. 合并排序的数组给定两个排序后的数组 A 和 B,其中 A 的末端有足够的缓冲空间容纳 B。示例:输入:输出: [1,2,2,3,5,6]说
依次比较数组中相邻两个元素大小,若 a[j] > a[j+1],则交换两个元素,两两都比较一遍称为一轮冒泡,结果是让最大的元素排至最后 重复以上步骤,直到整个数组有序 优化方式: 每轮冒泡时,最后一次交换索引可以作为...