标签目录:算法

以下是与标签 “算法” 相关联的文章

LRUMap的简单实现

定义: LRUMap使用最近最少使用算法,当一个元素添加或者被访问,就是最近最多使用的,内部维护一个列表,表头是最近最少使用的元素,表尾是最近最多使用的,当一个元素添加或者被访问时候,这个元素会被移动到列表表尾,而当元素数量达到最大的时候,会从表头删除一个原色。 实现: 12345678910111213141516171819202122……

按照权重返回数组中的数字

问题:有N个数字,每个数字有一个权重,例如:[1, 0.2] [5, 0.5] [8, 0.3], 要求按照权重来返回数字。 算法描述: 这个需要使用随机数产生数组索引,但是随机数产生的索引是均等概率的,由于需要按照权重来返回数字,我们需要舍弃一些数字,权重小得舍弃的多,权重大得舍弃的少。 算法: 1. 根据权重数组,生成权重次数数……

在多个源串中找到同位词

不考虑字母顺序,含有相同字符的单词称为同位词, 也有人称为兄弟单词,例如army和mary。本算法把输入的字符串按照字母顺序排序,然后,放入hash表,hash表的key是按字母顺序排序的字符串,值则是一个列表,列表是这些字母组成的多个同位词。 假设源数组有n个字符串,构造hash表需要O(n)的时间复杂度,查找则需要O(1)的复……

一亿个数字求top10

凡是求top多少的问题,基本都是使用堆排序,因为堆每次调整只需要log2k的时间复杂度,k是堆的大小,在此类题中是求最大或者最小的那些数字的数量,因此会将复杂度极大的进行简化。 假设一共有n个数字,求top k的数字,那么复杂度是O(nlog2k), 如果n = 100000000, k = 10, 计算得到100000000*log2^10 = 300000000, 也就是……

使用均等概率产生(0,1)的函数实现均等概率产生(0,1,2)的函数

这是一个同事和我一起讨论的一道概率方面的算法问题,边讨论边实现,在实现算法的时候对问题和解决方法都是注释满满的,代码也是自解释的,这里就不多说了,直接贴代码,看代码理解算法更可靠。 问题定义 123456789101112131415161718192021222324package com.robert.dsal.math.probability.conversion; import java.uti……

聚簇索引(InnoDB)快还是非聚簇(MyISAM)索引快

一个朋友问我聚簇索引快还是非聚簇索引快呢?这个问题其实很难回答,也很难进行一个实际的测试来判断到底哪个快,除了聚簇索引和非聚簇索引在原理上的不同,实际上一个存储引擎的索引快慢还受其实现方法和功能的影响,比如,事物,锁,高并发,存储策略,缓存策略等,本文就简单的从理论上进行分析,根据索引的实现原来来……

【转载】【经典】MySQL索引背后的数据结构及算法原理

本文系经典,转载自:http://www.uml.org.cn/sjjm/201107145.asp#nav-4-1   MySQL索引背后的数据结构及算法原理 张洋,发布于2011-07-14, 张洋的Blog 写在前面的话 在 编程领域有一句人尽皆知的法则“程序 = 数据结构 + 算法”,我个人是不太赞同这句话(因为我觉得程序不仅仅是数据结构加算法……