2080 区间内查询数字的频率
思路:首先理解题目,要我们写一个数据结构,也就是一个自定义类,需要有对应的元素,以及构造方法,还有一个公共方法query,用来求频次
一开始,我是将传入的数组再用一个数组来维护,我想的是再query函数里将我们的数组通过left和right进行切片,然后对切片数组进行排序,再将这个排序后的数组以及传过来的value进行二分查找,得到最左value位置,再查value+1,得到右边界,最后二者相减,即可得到结果,但是这样的解法会有用例超时
代码:
class RangeFreqQuery { private final int[] query; public RangeFreqQuery(int[] arr) { this.query = arr; } public int query(int left, int right, int value) { int[] nums = new int [right - left + 1]; for(int i = 0;i<nums.length;i++){ nums[i] = query[left + i]; } Arrays.sort(nums); int S = find(value,nums); int B = find(value+1,nums); return B - S; } private int find(int target,int[] nums){ int left = 0; int right = nums.length - 1; while(left <= right){ int mid = left + (right - left)/2; if(nums[mid] >= target){ right = mid - 1; }else{ left = mid + 1; } } return left; } }后面呢,也是看了灵神(灵茶山艾府)的题解,了解到优化的思路,构造这个数据结构时,我们可以将传过来的数组的元素加入一个map中,键是元素的值,值就是这个元素在原数组中的下标列表,这样呢,还可以保证我们的这个下标列表是有序的,此时我们有了目标元素对应的下标列表,我们的问题就转化为求目标值对应的下标列表中有多少元素在[left,right]中,我们就可以通过比较左右边界在列表中的位置,再计算得到符合要求的元素数量
具体操作:通过调用query时传的value去获取对应的下标列表,如果列表为空就直接返回0,那么我们就可以分别对传过来的两个边界与我们的下标列表进行二分查找,得到相对应在列表中的下标,最后将二者相减即可,这里要注意,我们对右边界的求值传的目标值应该是right+1,这样才能将两者的返回值直接相减,如果left比所有的元素都大,那两者得到的都是列表的长度,相减就是0,依然是正确的,反之同理
代码:
class RangeFreqQuery { private final Map<Integer,List<Integer>> pos =new HashMap<>(); public RangeFreqQuery(int[] arr) { for(int i = 0; i<arr.length;i++){ pos.computeIfAbsent(arr[i],k -> new ArrayList<>()).add(i); } } public int query(int left, int right, int value) { List<Integer> a = pos.get(value); if(a == null){ return 0; } return find(a,right + 1) - find(a,left); } private int find(List<Integer> a,int target){ int left = 0; int right = a.size() - 1; while(left<=right){ int mid = left + (right - left)/2; if(a.get(mid) >= target){ right = mid - 1; }else{ left = mid + 1; } } return left; } }对于pos.computeIfAbsent(arr[i],k->newArrayList<>()).add(i);
这句的作用就是,当arr[i]这个数字是第一次被添加到map中的时候,新建一个空列表去承接他的下标,无论键是第几次出现方法最终会返回这个列表对象(如果是第一次就返回空列表),然后拿这个对象去.add,也就是添加元素
