【题目描述】
Give you an integer array (index from 0 to n-1, where n is the size of this array, value from 0 to 10000) and an query list. For each query, give you an integer, return the number of element in the array that are smaller than the given integer.
Notice：We suggest you finish problem Segment Tree Build and Segment Tree Query II first.
给定一个整数数组 （下标由 0 到 n-1，其中 n 表示数组的规模，数值范围由 0 到 10000），以及一个 查询列表。对于每一个查询，将会给你一个整数，请你返回该数组中小于给定整数的元素的数量。
【注】在做此题前，最好先完成线段树的构造和线段树查询 II这两道题目。
【题目链接】
www.lintcode.com/en/problem/count-of-smaller-number/
【题目解析】
此题可以用排序+二分查找的方法来做。先对数组排序，然后对于每个查询，用二分查找在数组中进行查询，找到原数组中第一个比查询数大的数，然后再从后往前统计。
由于这道题目不是查找==而是选择第一个>(num)的数的位置，所以while语句里面可以把>和=归为同一个分支>=，因为(==)存在包含重复数(duplicate)的情况，所以要和>一样，end指针前移替换mid。
那么另一个分支<，除了将start后移，还要更新返回值res。
第二点，如果while循环的约束条件是start < end，假如循环到最后start = end - 1，并且num就在end呢？这时应该返回res = start + 1，推测前一步，start = end - 2的时候，end的前移只能到mid为止，不能是mid - 1，否则就跳过了可能为所求结果的mid。
【参考答案】
www.jiuzhang.com/solutions/count-of-smaller-number/
转载于:https://my.oschina.net/u/3776581/blog/1620285
分享到：
相关推荐
java lru leetcode LeetFlag Total Count #1715 Jan 9, 2021 Using vscode-leetcode logined via 3rd ...248 Count of Smaller number 我一开始的想法是用模板把A[] build 成segment tree，然后valu
python python_leetcode题解之1365_How_Many_Numbers_Are_Smaller
A straightforward program works well for a smaller number of towns and cities but seems to run forever on the actual problem, and improving the program turns out to be surprisingly hard. How come? ...
read array and read number 1-print the element larger than number 2-print the element smaller than number
number of radio frequency (RF) chains is usually much smaller than that of antennas. To date, several channel estimation schemes have been proposed for mmWave massive MIMO over narrowband channels, ...
The M.2 is a family of form factors that will enable expansion, contraction, and higher integration of functions onto a single form factor module solution. The key target for M.2 is to be ...
This file contains an example that show how to detect an object's distance and calculate the smallest distance.
number higher or lower 349: intersection of two arrays 350: intersection of two arrays ii medium 33: search in sorted array 81: search in rotated sorted array ii 153: find minimum in rotated sorted ...
7 The key target for M.2 is to be significantly smaller in the XYZ and overall volume of the Half-Mini 8 Card used today in mobile Platforms in preparation for the very thin computing Platforms 9 (e.g...
ApplicationofNatured-InspiredAlgorithmsfortheSolutionofComplexElectromagnetic Problems.............................................................................................
The number of questions is increasing recently. Here is the classification of all `468` questions. For more questions and solutions, you can see my [LintCode](https://github.com/kamyu104/LintCode) ...
java lru leetcode Java相关知识 基础知识 集合 多线程 JVM Spring 锁 ...LintCode相关必刷题目(转自面经) ...重点：快速排序、归并排序、堆排序（面试问排序基本就是这三个，理解并背熟） ...Smaller Numbers A
a smaller solution be run over a downsampled image. Although general purpose upsampling methods can be used to interpolate the low resolution solution to the full resolution, these methods generally ...
The features can be of any type and in any number of dimensions, and are defined by the user. The EMD is defined as the minimum amount of work needed to change one signature into the other. The ...
LintCode、LeetCode 等算法问题的 Java 解决方案。 一旦出现新问题或新测试用例，我将尝试修改解决方案。 顺序 问题 等级 语 0 [2 Sum II - 输入数组已排序.java]( Sum II - 输入数组已排序.java) Java 1 [2 Sum II....
LintCode、LeetCode 等算法问题的 Java 解决方案。 一旦出现新问题或新测试用例，我将尝试修改解决方案。 2016年年中，我意识到人们可能希望为此 repo 做出贡献，并通过提供修复程序、更好的解决方案等来使其更好。...
of holes in the"stone"lock.If the kev is smaller than the stonethen the key can be moved to any location relative to the stoneso ona as it doesn't extend bevond the edae of the stone in any ...
标题“Joany,Lo Speak Music Sound Smaller”和描述“Speak Music Sound Smaller”看起来像是一个音乐相关的软件或应用的名字，可能与音频处理、音乐制作或者声音调整有关。标签同样重复了这个短语，进一步强调了...
Keeping your clustered key value small increases the number of index rows that can be placed on an index page and decreases the number of levels that must be traversed. This minimizes I/O. As we’ll ...