查询L到R范围内有几个aim？

范围内有几个aim？"/>

查询L到R范围内有几个aim？

如何高效查询L到R范围内有几个aim

提示：本题是今日头条的面试题，利用二分法查询，经典得很
二分法，是大厂们极其喜欢考的方法

文章目录

• 如何高效查询L到R范围内有几个aim
• 题目
• 一、审题
• 二、解题
• • 暴力解0分
  • 二分查找最优解100分
• 总结

题目

给你一个arr，里面全是数字
再给你一个N*3的数组，一行代表一个查询query，前面俩数表示L,R范围，第3个数时aim
一个查询任务是：请你查询arr的L到R范围内有几个aim？
N行代表N个查询任务
请你设计算法，最后返回一个结果数组，表示N个查询任务中的每个aim个数

一、审题

示例：arr = 1 3 2 3 1 1 2 3 1
query =
0 3 1 0到3范围内有几个1？1个
1 6 2 1到6范围内有几个2？2个
4 7 3 4到7范围内有几个3？1个
1 8 4 1到8范围内有几个4？0个
请你返回ans = 1 2 1
读懂了吧？

二、解题

暴力解0分

显然，任何一个题目都可以暴力查询
N个查询任务，每一次要查询，可能把整个数组arr都遍历完，那不妨设arr长度为M
则时间负责度为o(N*M)，面试你这么写，必然0分

二分查找最优解100分

自然要想更好的办法，这里我借鉴左神的二分法，怎么设计呢?

你要去统计一个范围内的aim个数，那就需要看下标L–R，一个数组arr可能就只有很少的几个aim，干嘛要整个数组遍历呢，为何不利用aim来记录究竟哪些位置是出现过aim，这样就把出现过aim的下标i搞成一个列表了，这样就将查询的范围缩小了【而且，从左往右遍历去找aim，这些下标一定是有序的】。

一个查询任务：拿审题中那个arr做例子：用map记录，key代表arri，value是一个ArrayList代表从左往右，哪些下标i是arri

于是，你要查0 3 1 0到3范围内有几个1？只需要去取map中1的value列表出来
然后在0 4 5 8这个有序数组中查
——小于0的有几个数？a=0个
——小于3+1的有几个数？b=1个
结果就是b-a=1个

好，如何找一个有序数组中小于k的有几个数？二分法：【二分法自然复杂度o(log(M))】
看图，不妨设让你查1 2 3 4 5 6 7 8 9中小于4的有几个？

下标0–8，二分中点
第1次中点落在4，发现5?4,显然右边部分不可能有小于4的，所以需要去左边找
第2次中点落在1，发现2<4,显然左边全部小于4，而且右边还有可能<4，还需要右边继续找【但是先记录一个目前最右边小于4的坐标mR=1】
第3次中点落在2，发现3<4,显然左边全部小于4，而且右边还有可能<4，还需要右边继续找【但是先记录一个目前最右边小于4的坐标mR=2】
第4次中点落在4，结果不小于4，继续，发现L>R了，违规，跳出
有几个小于4呢？mR+1，因为下标是0开始的

好，手撕代码吧！
二分查找L–R上小于k有几个的代码：

//**如何找一个有序数组中小于k的有几个数？**二分法：public int countLessThan(ArrayList<Integer> arr, int k){int L = 0;int R = arr.size() - 1;int mR = -1;//如果最后mR仍然是-1，那mR+1==0，即没找到，0个while(L <= R) {int mid = L +((R - L) >> 1);//取中点if (arr.get(mid) < k){mR = mid;//还需要继续向右查找，不知道怎么定，就举例子一看就明白L = mid + 1;}else R = mid - 1;//否则就是arri>k,右边不可能，只能去左边找}//当L > R时跳出循环，此时mR记录了最右边那个<k的坐标return mR + 1;}

如何高效查询L到R范围内有几个aim的代码：
这里是这样的，我需要设计一个数据结构：QueryBox，
——它自带map属性，初始化传入arr，填好map
——自带二分查找那个函数：countLessThan(ArrayList arr, int k)
——自带查一个query的函数，查L–R上aim有几个？queryLRNum(int L, int R, int aim)
——自带遍历N个query任务时，返回一个数组ans：public int[] query(int[][] queryArr)
自然，N个查询任务的话，优化解的复杂度就是：o(N*log(M))
log(M)<<N,
故整体优化解速度就很快了，自然面试官才能青睐你的能力。
整体代码如下：

public static class QueryBox{//map统计arr的各个值aim都有哪些下标HashMap<Integer, ArrayList<Integer>> map;public QueryBox(int[] arr){//先统计arr的各个值aim都有哪些下标map = new HashMap<>();for (int i = 0; i < arr.length; i++) {if (!map.containsKey(arr[i])) map.put(arr[i], new ArrayList<>());map.get(arr[i]).add(i);//把i下标记录好}}//**如何找一个有序数组中小于k的有几个数？**二分法：public int countLessThan(ArrayList<Integer> arr, int k){int L = 0;int R = arr.size() - 1;int mR = -1;//如果最后mR仍然是-1，那mR+1==0，即没找到，0个while(L <= R) {int mid = L +((R - L) >> 1);//取中点if (arr.get(mid) < k){mR = mid;//还需要继续向右查找，不知道怎么定，就举例子一看就明白L = mid + 1;}else R = mid - 1;//否则就是arri>k,右边不可能，只能去左边找}//当L > R时跳出循环，此时mR记录了最右边那个<k的坐标return mR + 1;}//一个查询L--R上有几个aim的任务。// arr中现有一堆升序值，作为aim的下标，你要找下标在L到R上的有几个？public int queryLRNum(int L, int R, int aim){//大流程，先查arr上小于L的有几个？a// 再看arr上小于R + 1的有几个？b//返回b-a//注意拿list之前看看aim有吗，没有就返回0if (!map.containsKey(aim)) return 0;ArrayList<Integer> arr = map.get(aim);//从map中搞到下标listint a = countLessThan(arr, L);int b = countLessThan(arr, R + 1);return b - a;}//遍历N个任务public int[] query(int[][] queryArr){//然后遍历M个query任务int[] ans = new int[queryArr.length];//M行结果for (int i = 0; i < queryArr.length; i++) {int L = queryArr[i][0];int R = queryArr[i][1];int aim = queryArr[i][2];ans[i] = queryLRNum(L, R, aim);//查L--R范围上有几个aim}return ans;}}

测试代码：

//测试代码public static void test(){int[] arr = {1, 3, 2, 3, 1, 1, 2, 3, 1};int[][] query = {{0,3,1},{1,6,2},{4,7,3},{1,8,4}};QueryBox queryBox = new QueryBox(arr);//初始化int[] ans = queryBox.query(query);//直接拿着query数组查询for(Integer i : ans) System.out.print(i + " ");}public static void main(String[] args) {test();}

跑出来的结果没错：

1 2 1 0 

总结

提示：本题借鉴思路：

1）熟悉二分查找的经典思想和代码，非常重要的
2）当练习和见过大量的题目之后，你的数据结构与算法敏感度就会迅速提升，再见到新的题目时会很容易相同别人的有化解