当前位置: 首页 > article >正文

随机题两题

逆序对

题目

给定一个数组,求其中有多少逆序对,要求时间复杂度不超过nlogn。

思路

  • 使用归并排序的分治思想,将数组递归地分为左右两部分。
  • 在合并两个有序子数组时,若左侧数组中的某个数大于右侧数组中的某个数,则可以确定该左侧数组中的这个数和右侧数组中当前及其后的所有元素形成逆序对。
  • 递归合并的过程中,统计所有逆序对的数量。

代码

 private static int countInversions(int[] num) {
        int left = 0, right = num.length - 1;
        int[] temp = new int[num.length];
        return countSum(num,temp,left,right);
    }

    private static int countSum(int[] num, int[] temp, int left, int right) {
        if(left>=right){
            return 0;
        }
        int mid = left + (right - left) / 2;
        int count = countSum(num,temp,left,mid);
        count=count+countSum(num,temp,mid+1,right);
        count=count+countNum(num,temp,left,mid,right);
        return count;
    }

    private static int countNum(int[] num, int[] temp, int left, int mid,int right) {
        int i=left,j=mid+1;
        int k=0,count=0;
        while(i<=mid&&j<=right){
            if(num[i]<num[j]){
                temp[k++]=num[i++];
            }else{
                temp[k++]=num[j++];
                count = count+(mid-i+1);
            }
        }
        while(i<=mid){
            temp[k++]=num[i++];
        }
        while(j<=right){
            temp[k++]=num[j++];
        }
        for(int p=left;p<=right;p++){
            num[p]=temp[p];
        }
        return count;
    }

均衡

题目

这是一个通过移动数组元素值实现尽量“均衡”的问题。目标是使数组中元素尽量相等,或者趋于相同的范围。每次只能移动 1 单位,只能移动相邻的数组。

例如数组【1,4,6】,下标为1的数组元素4,可以移动移动一单位给1或者6,将数组变为【2,3,6】或者【1,3,7】。

要求数组达到【3,4,4】,数组顺序不限。

思路

直接一个模拟

  1. 不断调整相邻的元素,逐步趋近于配平。
  2. 打印每次移动的过程,直到达到平衡或接近平衡。

代码

public static void balanceArray(int[] arr) {
        int moves = 0;
        int n = arr.length;

        while (!isBalanced(arr)) {
            for (int i = 0; i < n - 1; i++) {
                if (arr[i] < arr[i + 1]) {
                    arr[i]++;
                    arr[i + 1]--;
                    moves++;
                    printArray(arr, moves);
                }
                else if (arr[i] > arr[i + 1]) {
                    arr[i]--;
                    arr[i + 1]++;
                    moves++;
                    printArray(arr, moves);
                }
            }
        }

        System.out.println("Total moves: " + moves);
    }

    private static boolean isBalanced(int[] arr) {
        int total = Arrays.stream(arr).sum();
        int remainder = total % arr.length;
        int first = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != first&&Math.abs(first-arr[i])>remainder) {
                return false;
            }
        }
        return true;
    }

    private static void printArray(int[] arr, int step) {
        System.out.println("Step " + step + ": " + Arrays.toString(arr));
    }


http://www.kler.cn/a/371531.html

相关文章:

  • Selenium自动化测试框架详解
  • Linux高阶——1026—验证内存映射mmap函数使用
  • 2024年医疗人工智能研究报告-生成式AI爆发,医疗人工智能走到新的十字路口(附下载)
  • 如何用猿大师办公助手实现OA系统中Word公文/合同在线编辑及流转?
  • SpringMVC实战:构建高效表述层框架
  • week08 zookeeper多种安装与pandas数据变换操作-new
  • 开源项目-投票管理系统
  • 苹果生态的机器学习和同态加密
  • Android 玩机知识储备
  • Java国际版同城打车顺风车滴滴车跑腿系统小程序源码
  • 《 Python 与股票大盘信息的奇妙之旅》
  • 深度学习案例:带有一个隐藏层的平面数据分类
  • 等保行业如何面对新兴安全威胁
  • MFC图形函数学习04——画矩形函数
  • rabbitmq高级特性(2)TTL、死信/延迟队列、事务与消息分发
  • day03|计算机网络重难点之HTTP中常见的状态码、什么是强缓存和协商缓存
  • 在Facebook运营中使用住宅IP的重要性
  • 您知道Apple公司的大模型(AFM)吗?
  • HTML5 应用程序缓存
  • 深度学习-36-基于PyTorch的卷积神经网络LeNet
  • nrm的使用
  • 移远通信闪耀2024香港秋灯展,以丰富的Matter产品及方案推动智能家居产业发展
  • Javaee:单例模式
  • ubuntu配置xrdp
  • Robotaxi砍掉的特斯拉市值,财报又赢回来了
  • 在 Node.js 中使用 .env 文件