算法真题-腾讯-逆序数字(3)

前言

今天做题目做了求逆序数字的个数，链接逆序数字然而我写的代码只能通过60%的测试案例，QWQ，先把它写出来mark一下，以后可以改进一下。

题目描述

作为程序员的小Q，他的数列和其他人的不太一样，他有 $2^n$ 个数。

老板问了小Q一共 m次，每次给出一个整数 $q_i(1<=i<=m)$ ，要求小Q把这些数每 $2^{q_i}$ 分为一组，然后把每组进行翻转，小Q想知道每次操作后整个序列中的逆序对个数是多少呢？

例如:

对于序列1 3 4 2，逆序对有(4, 2),(3, 2),总数量为2。

翻转之后为2 4 3 1，逆序对有(2, 1),(4, 3), (4, 1), (3, 1),总数量为4。

输入描述

第一行一个数n(0<=n<=20)

第二行 $2^n$ 个数，表示初始的序列（1<=初始序列<= $10^9$ ）

第三行一个数m（1<=m<= $10^6$ ）

第四行m个数表示 $q_i(0<=q_i<=n)$

输出描述

m行每行一个数表示答案。

输入例子

2
2 1 4 3
4
1 2 0 2

输出例子

0
6
6
0

解题思路

用到了二分查找，维护一个单调递增序列，讲一个数插入，看他插入的小标index，可以通过序列长度len-index来判断当前要插入的数字有多少个小于前面的数，比如数组[2 1 4 3]，假设我们遍历到4，此时递增序列是[1 2]，我们要把4插入到该递增序列中，插入后的索引是2，所以前面有len-2=0个数比4大，此时递增序列是[1 2 4]，当遍历到3时，插入到递增序列的索引时2，所以，前面有3-2=1个数比3大。

代码

package com.company;

import java.util.ArrayList;
import java.util.Scanner;

public class nixudui {
    public static void main(String[] args) {
//        输入数据
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int len = (int) Math.pow(2,n);
        int nums[] = new int[len];
        for(int i=0;i<len;i++){
            nums[i] = scanner.nextInt();
        }
        int m = scanner.nextInt();
        int[] m_nums = new int[m];
        for(int i=0;i<m;i++){
            m_nums[i] = (int) Math.pow(2,scanner.nextInt());
        }
        long[] result = new long[m];
        ArrayList<Integer> arrayList = new ArrayList<>();
        for(int i=0;i<m;i++){
//            #对数组进行逆序处理
            reverse(nums,m_nums[i]);
            arrayList.add(nums[0]);
            long count = 0;
            for(int j=1;j<len;j++){
                int index = bisect(arrayList,nums[j]);
                count += index;
            }
            result[i] = count;
//            重置arrayList
            arrayList.clear();
        }
        for(int i=0;i<m;i++){
            System.out.println(result[i]  + " ");
        }
//        System.out.println();

    }

    private static void reverse(int[] nums, int m_num) {
        int start = 0;
        int end = start + m_num;
        while(end<=nums.length){
            reverse(nums,start,end);
            start = end;
            end += m_num;
        }
    }
    private static void reverse(int[] nums, int start, int end){
        end--;
        while(start<end){
            swap(nums,start,end);
            start++;
            end--;
        }
    }

    private static void swap(int[] nums, int start, int end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
    }

    private static int bisect(ArrayList<Integer> arrayList, int num) {
        int size = arrayList.size();
        int start = 0, end = size-1;
        while(start <= end){
            int mid = start + (end - start)/2;
            if(arrayList.get(mid)<=num){
                start = mid + 1;
            }
            else{
                end = mid-1;
            }
        }
        arrayList.add(start,num);
        return size - start;
    }
}