【题目描述】
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
The length of A will not exceed 1000, and B will be smaller than 100000. Process to the end of file. Output For each test case, you have to ouput the result of A mod B. Sample Input 2 3 12 7 ...
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.
“Microsoft’s newest version of Exchange provides push email capability as a standard feature. However, its limited security and management capabilities require that companies add-on to the out-of...
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...
7za.exe supports a smaller number of compression formats
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) ...
redundant, in the sense that a smaller subset of the SV kernel is sufficient for the representation of increasing operators. We provide sufficient conditions for the existence of the basis ...
All software design is composition: the act of breaking complex problems down into smaller problems and composing those solutions. Most developers have a limited understanding of compositional ...
Lighting & Optics Session 11 Objective Understand some of the details of Lighting and Optics Optics – Image Quality Types of lens Lighting – Usage Techniques Filters More thorough Webinars and ...
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 ...
Speak Music Sound Smaller