菜鸟笔记
数组中只出现一次的数
问题一：在一个整数数组中，除了一个数之外，其他的数出现的次数都是两次，求出现一次的数，要求时间复杂度尽可能的小。例如数组{1,2,2,3,3,6,6},出现一次的数是1. 从题目的描述可以看出，数组中只有一个数字出现了一次，其他的数...
算法笔记 第16页
菜鸟
BitMap算法详解
所谓的BitMap就是用一个bit位来标记某个元素所对应的value，而key即是该元素，由于BitMap使用了bit位来存储数据，因此可以大大节省存储空间。 基本思想： 这此我用一个简单的例子来详细介绍BitMap算法的原理。假设...
布隆过滤器
如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速...
对一致性hash原理的理解
一致性hash算法解决的核心问题是，当solt数发生变化的时候能够尽量少的移动数据。该算法最早在《Consistent Hashing and Random Trees:Distributed Caching Protocols for R...
哈希的应用（位图，布隆过滤器）
位图（整型） 1.面试题 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数 中。【腾讯】 遍历，时间复杂度O(N) 排序(O(NlogN))，利用二分查找: logN 位图解决 数据是否在给定的...
八大排序算法及其优化
常见的排序算法 1. 直接插入排序 （1）算法基本思想 （2）特性总结： 元素集合越接近有序，直接插入算法的时间效率越高 时间复杂度：O(N^2) 空间复杂度：O(1)，它是一种稳定的排序算法 稳定性：稳定 （3）代码实现： void In...