华为笔试 5.11

第一题， 链接

    输出每一个位置，右边有几个小于他。比如7962，就输出【2 2 1 0】

    因为7右边有2个比他小，9有两个，6有1个，2有0个。

    总共有100000个数（n），每一个数范围【1-100000】。

    这个数据量暴力解肯定超时。

    暴力思路：从右往左，看当前有几个小于自己。n个位置，每次又要看右边所有的，肯定爆。

    当时可能的想法：

从后往前保存数据，然后对于一个新的数，他后面的已经进入这个数据结构里了，试试能不能快速得到答案。

最开始想的是  和 logn 有关的 结构。

（1）TreeSet有序表。能够很快的找到 《=当前数的值是多少，但好像告诉有多少个不太可行；

（2）自己实现堆。自己把数放到堆里，heapInsert、heapify去维护，自己可以设置反向索引表快速地找，但是吧毕竟他不是有序的，只能说一个值左侧、右侧，想了想算了。

（3）优先队列？好像也没有对应的函数。

此时都不可以，放松限制，这个数据结构不用排好序，我自己大不了插入排序就可以了。二分找<key最右侧的位置，然后***去，这样logn  自己维护也不亏啊！而且插入位置和前面有几个有对应关系的。

    比如测试用例  7 9 6 2

    刚开始自己的ArrayList放2.【2】

    来到6，二分发现，小于6最右的位置，是0，那我就知道有0+1个比6小，而且我只需要吧6插入到1位置就ok。

    此时【2 6】

    来到9，二分发现，小于9最右侧位置是1，我就知道有1+1个比9小，插入位置是1+1位置。

    此时【2 6 9】

    来到7，二分发现，小于7最右侧位置是1，（6《7《9），我就知道有1+1个比7小，并且插入位置是1+1位置。

    此时【2 6 7 9】

    打完收工，自己维护自己找，吧插入和查找同时处理，肯定可以的。

public static void main(String[] args) {
        //erfen1weizhi
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = in.nextInt();
        }
        int[] ans = new int[n];

        List<Integer> list = new ArrayList<>();
        list.add(arr[n-1]);

        for(int i = n-2; i >= 0; i--){
            int size = list.size();
            int aim = arr[i];

            //找 小于等于自己 最大的那个值
            int l = 0, r = size-1;
            int b = -1;
            while(l <= r){
                int mid=l+(r-l)/2;
                if(list.get(mid) < aim){
                    b = mid;
                    l = mid + 1;
                }else {
                    r = mid - 1;
                }
            }

            if(b == -1){
                ans[i] = 0;
            }else{
                ans[i] = b+1;
            }

            b = b==-1 ? 0 : b+1;
            list.add(b, aim);


        }
        for(int i = 0; i < n-1; i++){
            System.out.print(ans[i]+" ");
        }
        System.out.println(ans[n-1]);


    }

第二题，题目问题很大 且找不到入口反馈。

    大概问题是，一个旗子的气定义为周围有多少个空位置，相同颜色的视为一批，这一批气共享。如果气>=2 认为合法。返回合法黑色、白色的数量。

    如果题目没问题的话，思路就是 并查集。每个位置先统计一下气是多少，并查集合并的时候把气也合并。最后统计气》=2的就可以。

    这个出题者不细心，题目说n*n，然后第二个测试用例就来了30个旗子，说按照N*N摆放可以摆成5*6的。     然后有意思的来了，测试用例2，输出答案是black 2 white 9，紧跟着输出解释说，黑色旗子活子数量是2，白色旗子活子数量是10。 可是10 ！= 9啊。

    反馈通道都没有。

第三题来不及