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;
    }
}