首页 > 其他分享 >一道神奇的面试题---无序数组排序后的最大相邻差

一道神奇的面试题---无序数组排序后的最大相邻差

时间:2024-04-28 13:44:04浏览次数:23  
标签:面试题 min int max buckets --- 数组 array 排序

一:概述

  这个算法的面试题目是:有一个无序整型数组,如何求出该数组排序后的任意两个相邻元素的最大差值?要求时间和空间复杂度尽可能低。  

  

 

 

二:具体说明

  <1>第一种解法(初步解法)

    这个解法的大致思路:使用任意一种时间复杂度为O(nlogn)的排序算法(如快速排序)给原数组排序,然后遍历排好序的数组,并对每两个相邻元素求差,最终得到最大差值。这个解法的时间复杂度是O(nlogn),在不改变原数组的情况下,空间复杂度是O(n)。

   <2>第二种解法

    利用计数排序的思想,先求出原数组的最大值max与最小值min的区间长度K(k=max-min+1),以及偏移量d=min.

  •     创建一个长度为k的新数组Array。
  •     遍历原数组,每遍历一个元素,就把新数组Array对应的下标值+1。例如原数组元素的值为n,则将Array[n-min]的值加1.遍历结束后,Array的一部分元素值变成了1或者更高的数值,一部分元素值仍然是0.
  •     遍历新数组Array,统计出Array中最大连续出现0值得次数+!,即为相邻元素最大差值。

    例如:给定一个无序数组{2, 6, 3, 4, 5, 10, 9},处理过程如图所示:
    第一步,确定k(数组长度)和d(偏移量).

      

    第二步,创建数组     

      

     第三步,遍历原数组,对号入座。

 

    第四步,判断0值最多连续出现的次数,计算出最大相邻差。

       <3>第三种解法

  1.       利用桶排序得思想,根据原数组得长度n,创建出n个桶,每一个桶代表一个区间范围。其中第1个桶从原数组得最小值min开始,区间跨度是(max - min)/(n -1)。
  2.       遍历原数组,把原数组每一个元素插入到对应的桶中,记录每一个桶的最大和最小值。
  3.       遍历所有的桶,统计出每一个桶的最大值,和这个桶右侧非空桶的最小值的差,数值最大的差即为原数组排序后的相邻最大差值。

    例如:给出一个无序数组{2, 6, 3, 4, 5, 10, 9},处理过程如下所示:
    第一步,根据原数组,创建桶,确定每个桶的区间范围。

     第二步,遍历原数组,确定每个桶内的最大和最小值。

     第三步,遍历所有的桶,找出最大相邻差。

 最大相邻差= 9 -6 = 3

这个方法不需要像标准桶排序那样给每一个桶内部进行排序,只需要记录桶内的最大和最小值即可,所以时间复杂度稳定在O(n)

package com.algorithm6;
/**
 *无序数组排序后的最大相邻差
 */
public class UnsortArrayOfMaxDistance1 {
    public static int getMaxSortedDistance(int[] array) {
        // 得到数列的最大值和最小值
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
            }
            if (min > array[i]) {
                min = array[i];
            }
        }
        int d = max - min;
        // 如果max和min相等,说明数组所有元素都相等,返回0
        if (d == 0) {
            return 0;
        }

        // 初始化桶
        int bucketNum = array.length;
        Bucket[] buckets = new Bucket[bucketNum];
        for (int i = 0; i < bucketNum; i++) {
            buckets[i] = null; // 初始化为null
        }

        // 确定数组元素所归属的桶下标
        for (int i = 0; i < array.length; i++) {
            int index = ((array[i] - min) * (bucketNum - 1) / d);
            if (buckets[index] == null) {
                buckets[index] = new Bucket(); // 如果桶是null,先创建一个新的桶
            }
            // 更新桶的最小值和最大值
            if (buckets[index].min == null || buckets[index].min > array[i]) {
                buckets[index].min = array[i];
            }
            if (buckets[index].max == null || buckets[index].max < array[i]) {
                buckets[index].max = array[i];
            }
        }

        // 遍历桶,找到最大差值
        int leftMax = buckets[0].max;
        int maxDistance = 0;
        for (int i = 1; i < buckets.length; i++) {
            if (buckets[i] == null) {
                continue;
            }
            if (buckets[i].min - leftMax > maxDistance) {
                maxDistance = buckets[i].min - leftMax;
            }
            leftMax = buckets[i].max;
        }
        return maxDistance;
    }

    private static class Bucket {
        Integer min;
        Integer max;
    }

    public static void main(String[] args) {
        int[] array = new int[]{2, 6, 3, 4, 5, 10, 9};
        System.out.println(getMaxSortedDistance(array));
    }



}

 

 

 

 

 

 

 

 

 

 

 

  

 

标签:面试题,min,int,max,buckets,---,数组,array,排序
From: https://www.cnblogs.com/lyy123-Ly/p/18163583

相关文章

  • leedcode-
    自己写的:classSolution:defaddStrings(self,num1:str,num2:str)->str:#将两个字符串转换为整数num1_int=self.strToInt(num1)num2_int=self.strToInt(num2)#将两个整数相加,并将结果转换为字符串res=......
  • 系统之间的一致性问题 -- 支付成功显示未支付
    系统之间的一致性问题--支付成功显示未支付:接入第三方系统的支付接口,支付成功后,却显示未支付。这种一般是系统之间的状态不一致导致的。问题分析:先查看第三方系统的支付状态。如果第三方系统的支付状态也是未支付,那么说明第三方系统的状态有问题。如果第三方系统的支付状......
  • 开源相机管理库Aravis例程学习(五)——camera-api
    目录简介例程代码函数说明arv_camera_get_regionarv_camera_get_pixel_format_as_stringarv_camera_get_pixel_formatARV_PIXEL_FORMAT_BIT_PER_PIXEL简介本文针对官方例程中的:03-camera-api做简单的讲解。并介绍其中调用的arv_camera_get_region,arv_camera_get_pixel_format_as......
  • 网页布局------几种布局方式
    1、认识布局(1)确认页面的版心宽度版心是指页面的有效使用面积,主要元素以及内容所在的区域,一般在浏览器窗口中水平居中显示。在设计网页时,页面尺寸宽度一般为1200-1920排序。但是为例适配不同分辨率的显示器,一般版心宽度为1000-1200px。例如,屏幕分辨率为1021*768的浏览器,在浏览器......
  • Chrome-selenium IDE UI自动化
         随着日益发展,自动化测试,逐渐成为测试工程师必要掌握条件之一,自动化测试分为UI自动化、接口自动化。本文这里介绍的WEB网页UI自动化,依托于浏览器插件实现UI自动化,纯小白都可以实现,无需代码功底。非常有趣的小工具。 首先,我们需要在插件市场下载一个插件,Chrome-se......
  • MUR1060D-ASEMI开关电源专用MUR1060D
    编辑:llMUR1060D-ASEMI开关电源专用MUR1060D型号:MUR1060D品牌:ASEMI封装:TO-252正向电流(IF):10A反向电压(VRRM):600V正向电压(VF):1.30V工作温度:-55°C~150°C恢复时间:35ns芯片个数:1引脚数量:4芯片尺寸:86mil浪涌电流(IFMS):170AMUR1060D特性:恢复时间短性能稳定正向压降低参数一......
  • 01-linu核心基础-03操作系统基础
    在PC领域,苹果在2005年之前采用IBMPowerPC芯片,从2005-2020年采用Intelx86芯片,最近则新发布了苹果M1芯片。M1是一款基于ARM架构的苹果自研芯片。本文简单介绍苹果M1芯片及新产品布局对ARM生态影响windwos电脑是x86架构的Macosm芯片是基于arm架构的GPU(GraphicsProcessingUn......
  • Vue系列---【如何关闭eslint校验?】
    如何关闭eslint校验?1.如果你的项目集成了eslint,但校验太严格,导致项目启动不了,你没时间排错,你可以找到vue.config.js,没有就创建,配上下面的内容。module.exports={//关闭eslint,因为校验太严格,例如:在main.js里定义了一个变量leta=100;,但未使用,就会导致项目启动不了......
  • Go-Zero微服务快速入门和最佳实践(一)
    前言并发编程和分布式微服务是我们Gopher升职加薪的关键。毕竟Go基础很容易搞定,不管你是否有编程经验,都可以比较快速的入门Go语言进行简单项目的开发。虽说好上手,但是想和别人拉开差距,提高自己的竞争力,搞懂分布式微服务和并发编程还是灰常重要的,这也是我今年更新文章的重点。......
  • sudo: apt-get: command not found
    sudo:apt-get:commandnotfoundhttps://blog.csdn.net/zhengzhaoyang122/article/details/136132952问题LinuxRedHat执行sudo卸载nginx时,出现commandnotfound错误[root@iZuf65h6i43ltlzhqolumyZlocal]#sudoapt-getremovenginxsudo:apt-get:commandnotfound12解......