package com.model.array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
/**
* @Description:测试类
* @Author: 张紫韩
* @Crete 2021/9/2 23:23
* 给你一个数组arr
* 再给你一个[0,3,2] 查询数组arr从0到3有几个2
* 给你一个：[[0,3,2],[0,4,2],[1,3,2]]
* 输出结果
*/
public class ArrayDemo09 {
public static void main(String[] args) {
int[] arr={1,1,2,3,4,5,1,6};
int[][] matrix={{0,3,1},{0,6,1}};
System.out.println(Arrays.toString(getArr(arr, matrix)));
}
// 的到最终结果
public static int[] getArr(int[] arr,int[][] matrix){
// 得到数组中各个数在数组中的所有的下标，获取这张表
HashMap<Integer, ArrayList<Integer>> table = getTable(arr);
int[] resInt = new int[matrix.length];
int index=0;
for (int[] temp:matrix){
int left=temp[0];
int right=temp[1];
int target=temp[2];
resInt[index++]=getCount(table, target, left, right);
}
return resInt;
}
// 返回每个数和他的对用的出现下标的一张表
public static HashMap<Integer,ArrayList<Integer>> getTable(int[] arr){
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
ArrayList<Integer> list;
if (!map.containsKey(arr[i])){
list = new ArrayList<>();
}else {
list = map.get(arr[i]);
}
list.add(i);
map.put(arr[i],list);
}
// for (Integer key:map.keySet()){
// System.out.println(key+"\t"+map.get(key));
// }
return map;
}
//返回在right和left之间有几个数
public static int getCount(HashMap<Integer,ArrayList<Integer>> table,int target,int left,int right){
ArrayList<Integer> list = table.get(target);
return small(list,right+1)-small(list,left);
}
// 返回list中小于index的有几个
public static int small(ArrayList<Integer> list,int index){
int l=0;
int r=list.size()-1;
int res=-1;
while (l<=r){
int mid=l+(r-l)/2;
if (list.get(mid)<index){
res=mid;
l=mid+1;
} else {
r=mid-1;
}
}
return res+1;
}
}