算法思路: 在排好序的数组,相同的数字是排列在一起的,所以只需要找到key的左边界和右边界即可。
找左边界可以看成是找数组中第一个大于等于key的数的位置,找右边界可以看成是找最后一个小于等于key的数。
复杂度分析:时间复杂度是O(log(n)),空间复杂度是O(n)。
#include <stdio.h>
/*
* @brief 在升序数组a中找到第一个大于等于key的数的位置,如果不存在这样的位置,例如
* 数组a中所有的数字都比key小,则返回的数是n
* @parma int* a 升序数组
* @parma int n 数组a的长度
* @int key 待查找的关键字
*/
int find_left(int* a, int n, int key){
int l, r, mid;
l = 0;
r = n-1;
while(l <= r){
int mid = (l+r) >> 1;
if(a[mid] >= key) r=mid-1;
else l=mid+1;
}
return r+1;
}
/*
* @brief 在升序数组a中找到最后一个小于等于key的数的位置,如果不存在这样的位置,例如
* 数组a中所有的数字都比key大,则返回的数是-1
* @parma int* a 升序数组
* @parma int n 数组a的长度
* @int key 待查找的关键字
*/
int find_right(int* a, int n, int key){
int l, r, mid;
l = 0;
r = n-1;
while(l <= r){
int mid = (l+r)>>1;
if(a[mid] <= key) l = mid + 1;
else r = mid - 1;
}
return l-1;
}
int count(int* a, int n, int key){
int l = find_left(a, n, key);
int r = find_right(a, n, key);
int cnt = r-l+1;
return cnt;
}
int main(){
//输入和输出重定向
freopen("in.txt","r", stdin);
freopen("out.txt", "w", stdout);
const int N = 4;
int a[N] = {2, 4, 4, 5}, key;
//use case 1:key比数组中所有的数都要小
key = 1;
printf("%d出现的次数是%d\n", key, count(a, N, key));
//use case 2:key在数组出现了一次
key = 2;
printf("%d出现的次数是%d\n", key, count(a, N, key));
//use case 3:key在数组出现了不止一次
key = 4;
printf("%d出现的次数是%d\n", key, count(a, N, key));
//use case 4:key不在数组中,但大于数组中的最小数,小于数组中的最大数
key = 3;
printf("%d出现的次数是%d\n", key, count(a, N, key));
//use case 5:key比数组中的最大数还大
key = 6;
printf("%d出现的次数是%d\n", key, count(a, N, key));
return 0;
}
输出结果如下:
1出现的次数是0
2出现的次数是1
4出现的次数是2
3出现的次数是0
6出现的次数是0
分享到:
相关推荐
java求一个整数的因子 如题。 Java生成密钥的实例 1个目标文件 摘要:Java源码,算法相关,密钥 Java生成密钥、保存密钥的实例源码,通过本源码可以了解到Java如何产生单钥加密的密钥(myKey)、产生双钥的密钥对...
本文实例讲述了js获取对象,数组所有属性键值(key)和对应值(value)的方法。分享给大家供大家参考,具体如下: [removed] var values=function(object) { var values = []; for (var property in object) values....
向json中添加无key值数组的方法.txt
key_case -- 返回字符串键名全为小写或大写的数组 array_chunk -- 将一个数组分割成多个 array_combine -- 创建一个数组,用一个数组的值作为其键名,另一个数组的值作为其值 array_count_values -- 统计数组中所有...
实例如下: var aaa = { "0":"a", "1":"b", "2":"c", ...以上这篇js判断数组key是否存在(不用循环)的简单实例就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持软件开发网。
数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。 两种方式: 1...
主要是介绍了js将两个数组合并为类json方式,需要的朋友可以参考下
从对象数组中获取第一次出现的key的值。 使用安装 npm i pick-from --save 用法 var pickFrom = require ( 'pick-from' ) ; pickFrom ( 'a' , [ { b : 'c' } , { a : 'd' } ] ) //=> 'd' 将true作为最后一个参数...
实现一个“可变长二维数组”,这个二维数组的行数可由输入决定,每行的元素个数仍可由输入决定。每个数组元素值都是1. 执行结果如下: 请输入行数: 5 请输入第1行的元素个数: 20 请输入第2行的元素个数: 34 请...
下面小编就为大家带来一篇根据key删除数组中指定的元素实现方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
js基础代码实现
js代码-获取对象数组的一个key
js代码-数组key第一个转为大写
js代码-根据key相同合并对象,放进新的数组中
实现一个“可变长二维数组”,这个二维数组的行数可由输入决定,每行的元素个数仍可由输入决定。每个数组元素值都是1. 执行结果如下: 请输入行数: 5 请输入第1行的元素个数: 20 请输入第2行的元素个数: 34 请...
c代码-创建一个函数 search_idx ,将和有 n 个元素的数组 n 中,与 key 相等的元素的下标,储存在数组 idx 中。并返回和 key 相等的元素的个数。
JS中复合数组associative array和对象是等同的,判断一个key是否存在于数组中(或对象是否包含某个属性),不能使用ary[key] == undefined,因为可能存在ary = {key:undefined};正确的方法应该为: ary.hasOwnProperty...
关联数组指的是一个键值对应一个值,并且这个键值是不规律的,通常都是我们自己指定的。 他们两还有不同的地方,索引数组转为json后是数组。而关联数组转为json后是对象。通常我们给app端写接口都是用索引数组转成...