首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    Leetcode 295. Find Median from Data Stream

    在一个有序数组中找中位数,但需要支持再数组中添加新的元素。本来是有序里的,可以很轻易就查到中位数,但如果添加新数字后,不一定有序。如果先对数组排序,那代价就比较大了,每次排序时间复杂度O(n*log(n)),看discuss发现了一种很巧妙的解法,可以把添加数据的时间复杂度降低到O(log(n)) ,查询中位数O(1)。   这里我们需要用到优先队列,java里有现场的优先队列。准备两个优先队列,large里存比中位数大的数,small里存比中位数小的数。加入现在有n个数,large里存最大的n/2个数,很容易理解。但small里怎么存最小的n/2个数? 这里有个很巧妙的地方,把数组里数取负存到small里,small优先队列里其实存的是数组中取负后最大的n/2个数,不就是原数组中最小的n/2个数吗?需要特别考虑到n位奇数时,large里存了n/2+1个数,small里存了n/2个数(其实多余的一个也存small里)。算中位数的时候,如果n为奇数,直接从large里去第一优先级的就好了,如果n是偶数,从large和small里各取一个求平均,注意small里取出的数要取负变换之后才能用。   代码如下,

    01

    2019Java面试题:为什么使用hashmap需要重写hashcodes和equals方法?

    总的来说,Java中的集合(Collection)有两类,一类是List,再有一类是Set。你知道它们的区别吗?前者集合内的元素是有序的,元素可以重复;后者元素无序,但元素不可重复。那么这里就有一个比较严重的问题了:要想保证元素不重复,可两个元素是否重复应该依据什么来判断呢?这就是Object.equals方法了。但是,如果每增加一个元素就检查一次,那么当元素很多时,后添加到集合中的元素比较的次数就非常多了。也就是说,如果集合中现在已经有1000个元素,那么第1001个元素加入集合时,它就要调用1000次equals方法。这显然会大大降低效率。

    04

    ISBN号码

    问题描述 试题编号: 201312-2 试题名称: ISBN号码 时间限制: 1.0s 内存限制: 256.0MB 问题描述: 问题描述   每一本正式出版的图书都有一个ISBN号码与之对应,ISBN码包括9位数字、1位识别码和3位分隔符,其规定格式如“x-xxx-xxxxx-x”,其中符号“-”是分隔符(键盘上的减号),最后一位是识别码,例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言,例如0代表英语;第一个分隔符“-”之后的三位数字代表出版社,例如670代表维京出版社;第二个分隔之后的五位数字代表该书在出版社的编号;最后一位为识别码。   识别码的计算方法如下:   首位数字乘以1加上次位数字乘以2……以此类推,用所得的结果mod 11,所得的余数即为识别码,如果余数为10,则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的:对067082162这9个数字,从左至右,分别乘以1,2,…,9,再求和,即0×1+6×2+……+2×9=158,然后取158 mod 11的结果4作为识别码。   编写程序判断输入的ISBN号码中识别码是否正确,如果正确,则仅输出“Right”;如果错误,则输出是正确的ISBN号码。 输入格式   输入只有一行,是一个字符序列,表示一本书的ISBN号码(保证输入符合ISBN号码的格式要求)。 输出格式   输出一行,假如输入的ISBN号码的识别码正确,那么输出“Right”,否则,按照规定的格式,输出正确的ISBN号码(包括分隔符“-”)。 样例输入 0-670-82162-4 样例输出 Right 样例输入 0-670-82162-0 样例输出 0-670-82162-4

    01
    领券