算法真题-腾讯-逆序数字(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;
    }
}
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。