Leetcode算法题练习（一）-阿里云开发者社区

一、位图的引入

我们先来看一道题。

题目描述：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

思路一：遍历

拿到这道题，我们最先想到的方法就是直接遍历了。从头到尾遍历一遍，一定可以判断出一个数是否在其中。时间复杂度为 o(N)。

思路二：排序+二分查找

时间复杂度为排序 o(N*logN) + 二分查找 o(logN)。

思路三：位图

上面两种方法很常用，但是在面对40亿个数据时，无论是空间复杂度还是时间复杂度都很大。那么有没有比它们更加优秀的方法呢？

这里，我们就可以用位图去帮助我们解决这个问题：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。

二、概念

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用

来判断某个数据存不存在的。

如下图就是一个位图

三、位图的实现

在标准库里也是实现了位图的。

上图只截取了它的三个主要操作。下面我们分别来讲一讲它的三个操作。

1、set

set的作用是将x对应的比特位置设为1，表示其存在。相当于插入的作用。

void set(size_t x)
{
  size_t i = x / 8;
  size_t j = x % 8;
  _bits[i] |= (1 << j);
}

2、reset

reset的作用是将x对应的比特位置设为0，用来表示删除。

void reset(size_t x)
{
  size_t i = x / 8;
  size_t j = x % 8;
  _bits[i] &= ~(1 << j);
}

3、test

test的作用是用来查看x在不在。

bool test(size_t x)
{
  size_t i = x / 8;
  size_t j = x % 8;
  return _bits[i] & (1 << j);
}

4、位图实现

#pragma once
#include<iostream>
#include<vector>
using namespace std;
namespace zdl
{
  template<size_t N>
  class bitset
  {
  public:
    bitset()
    {
      _bits.resize(N / 8 + 1, 0);
    }
    void set(size_t x)
    {
      size_t i = x / 8;
      size_t j = x % 8;
      _bits[i] |= (1 << j);
    }
    void reset(size_t x)
    {
      size_t i = x / 8;
      size_t j = x % 8;
      _bits[i] &= ~(1 << j);
    }
    bool test(size_t x)
    {
      size_t i = x / 8;
      size_t j = x % 8;
      return _bits[i] & (1 << j);
    }
  private:
    vector<char> _bits;
  };
  void test01()
  {
    bitset<100> bs;
    bs.set(8);
    bs.set(9);
    bs.set(20);
    cout << bs.test(8) << endl;
    cout << bs.test(17) << endl;
        bs.reset(8);
    cout << bs.test(8) << endl;
  }
}

四、位图的应用

我们直接来看相关的题。

1、给定 100 亿个整数，设计算法找到只出现一次的整数。

我们首先来分析一下：我们需要从100亿个整数中，找到只出现一次的整数，数据量很大，那么我们就可以考虑使用位图的思想。而且这些数有三种状态，即：出现0次，1次以及1次以上。所以说我们只要保存一个数是否是三种状态的一种。但是，位图只能有两种状态：存在或者不存在。那么我们应该怎么解决这个问题呢？

这里我们就可以使用两个位图来帮助我们存储三种状态。如下图：

template<size_t N>
class twobitset
{
public:
  void set(size_t x)
  {
    if (!_bs1.test(x) && !_bs2.test(x))//00
    {
      _bs2.set(x);//01
    }
    else if (!_bs1.test(x) && _bs2.test(x))//01
    {
      _bs1.set(x);
      _bs2.reset(x);//10
    }
    //10不变
  }
private:
  bitset<N> _bs1;
  bitset<N> _bs2;
};

2、给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件的交集？

思路：将两个文件中的整数分别映射到两个位图中，然后将两个位图按位与，得到一个位图，如果这个位图的某个位上是1，那这个就是交集。

五、布隆过滤器

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。如何快速查找呢？

1、布隆过滤器的引入

针对上面的问题，我们有如下的解决方法：

1、用哈希表存储用户记录，缺点：浪费空间。

2、用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。（不同的字符串，转化成整型后，可能会映射到相同的位置）

而解决这类问题的最好方法，就是使用布隆过滤器。将哈希与位图结合，即布隆过滤器。

2、概念

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

根据上图，我们可以简单总结一下布隆过滤器的思想：同一个数据，根据不同的哈希函数转换成不同的整型，来映射到不同的位。也就是说同一个数据会映射多个位。这样就可以区分不同的字符串了。当然，也不排除不同字符串任然会映射到完全相同位置的可能。但是，哈希函数越多，可能性越小。

我们首先根据大佬们总结出来的算法，来确定几个哈希函数（这里我们确定三个）。

struct BKDRHash
{
    size_t operator()(const string& s)
    {
        // BKDR
        size_t value = 0;
        for (auto ch : s)
        {
            value *= 31;
            value += ch;
        }
        return value;
    }
};

struct APHash
{
    size_t operator()(const string& s)
    {
        size_t hash = 0;
        for (long i = 0; i < s.size(); i++)
        {
            if ((i & 1) == 0)
            {
                hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
            }
            else
            {
                hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
            }
        }
        return hash;
    }
}

struct DJBHash
{
    size_t operator()(const string& s)
    {
        size_t hash = 5381;
        for (auto ch : s)
        {
            hash += (hash << 5) + ch;
        }
        return hash;
    }
};

3、实现

* 基本框架

template<size_t N,
        class K = string,
        class HashFunc1 = BKDRHash,
        class HashFunc2 = APHash,
        class HashFunc3 = DJBHash>
class BloomFilter
{
public:
private:
  const static size_t _ratio = 5;
  bitset<_ratio* N> _bits;
};

* 插入：set

void Set(const K& key)
{
  size_t hash1 = Hash1()(key) % (_ratio * N);
  _bits.set(hash1);
  size_t hash2 = Hash2()(key) % (_ratio * N);
  _bits.set(hash2);
  size_t hash3 = Hash3()(key) % (_ratio * N);
  _bits.set(hash3);
}

* 查找：test

bool Test(const K& key)
{
  size_t hash1 = Hash1()(key) % (_ratio * N);
  if (!_bits.test(hash1))
    return false;
  size_t hash2 = Hash2()(key) % (_ratio * N);
  if (!_bits.test(hash2))
    return false;
  size_t hash3 = Hash3()(key) % (_ratio * N);
  if (!_bits.test(hash3))
    return false;
  return true;
}

* 删除

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。

4、布隆过滤器的优点

1、增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关。

2、哈希函数相互之间没有关系，方便硬件并行运算。

3、布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势。

4、在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势。

5、布隆过滤器的缺点

1、有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)。

2、不能获取元素本身。

3、一般情况下不能从布隆过滤器中删除元素。

4、如果采用计数方式删除，可能会存在计数回绕问题。

六、哈希切割

我们直接来看一个问题

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？如何找到top K的IP？

思路：读取每个ip，算哈希值 i = hash(ip) % 100，这个ip进入第i个小文件（相同的ip，一定进入相同的文件），利用 map<string, int>，对每个小文件统计次数。

若要寻找top K 的 ip，建一个K个值为<ip, cout>的小堆，去解决top K问题。

Leetcode算法题练习（一）