Lintcode---统计比给定整数小的数的个数
2024-09-04 11:08:11
给定一个整数数组 (下标由 0 到 n-1,其中 n 表示数组的规模,数值范围由 0 到 10000),以及一个 查询列表。对于每一个查询,将会给你一个整数,请你返回该数组中小于给定整数的元素的数量。
您在真实的面试中是否遇到过这个题?
Yes
样例
对于数组 [1,2,7,8,5]
,查询 [1,8,5]
,返回 [0,4,2]
思路1:先构造出一个符合问题查询需求的线段树。也就是区间内小于某数的值得个数作为额外属性;
在这里,求得额外属性的时候,可以借鉴线段树构造||中构造的最大值的线段树。
思路2:这题没有必要用线段树,写起来多麻烦,可以直接二分查找,代码简洁才是王道;
先做排序,然后查询;这里直接调用lower_bound函数;
函数lower_bound()在begint和end中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。
在这里,求得额外属性的时候,可以借鉴线段树构造||中构造的最大值的线段树。
思路2:这题没有必要用线段树,写起来多麻烦,可以直接二分查找,代码简洁才是王道;
先做排序,然后查询;这里直接调用lower_bound函数;
函数lower_bound()在begint和end中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。
class Solution {
public:
/**
* @param A: An integer array
* @return: The number of element in the array that
* are smaller that the given integer
*/
/*
思路1:先构造出一个符合问题查询需求的线段树。也就是区间内小于某数的值得个数作为额外属性;
在这里,求得额外属性的时候,可以借鉴线段树构造||中构造的最大值的线段树。 思路2:这题没有必要用线段树,写起来多麻烦,可以直接二分查找,代码简洁才是王道; 先做排序,然后查询;这里直接调用lower_bound函数; 函数lower_bound()在begint和end中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。
*/ vector<int> countOfSmallerNumber(vector<int> &A, vector<int> &queries) {
// write your code here sort(A.begin(),A.end());
vector<int> ret;
for(int q:queries){
int cnt = lower_bound(A.begin(),A.end(),q)-A.begin();
ret.push_back(cnt);
}
return ret;
}
};
最新文章
- SpringMVC介绍之Validation
- c++截取英文和汉字(单双字节)混合字符串
- C# vba 操作 Word
- pcr free library 介绍
- 用彩虹表破解MD5、LM Hash等复杂加密密码
- redhat 安装virtualbox
- Aliyun EMR 集群重启
- 平板点餐软件编程体会---记我的Android编程之路
- asp.net 程序,当发生找不到文件的错误时,如何正确定位是哪个文件?
- bzoj 4237: 稻草人
- awk打印第n个参数到最后一个技巧/将n行组成一列
- 渗透测试,form对象类型转换,简单demo
- php过滤&;nbsp;字符
- 深入理解JAVA中的NIO
- adb Android Debug Bridge 安卓调试桥
- string.replace替换
- Leaving Auction CF 749D
- 用node.js写的代码
- javascript时钟代码 DEMO-002
- 《DSP using MATLAB》Problem 2.15
热门文章
- bootstrap学习(全局CSS样式)(二)
- <;摘录>;算法策略的总结
- <;摘录>;MBR和分区表
- c/c++代码的unit-test中覆盖率的统计
- [转] Moran&#39;s I
- mysql 中添加索引的三种方法
- Java构造和解析Json数据的两种方法详解一——json-lib
- redux状态管理和react-redux的结合使用
- python部署工具fabric
- 【OpenGL】用OpenGL shader实现将YUV(YUV420,YV12)转RGB-(直接调用GPU实现,纯硬件方式,效率高)