• 哈希----位图

    位图

    位图概念

    1. 面试题
    给 40 亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这 40 亿个数中。【腾讯】
    1. 遍历，时间复杂度 O(N)
    2. 排序 (O(NlogN)) ，利用二分查找 : logN
    3. 位图解决
    数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比
    特位来代表数据是否存在的信息，如果二进制比特位为 1 ，代表存在，为 0 代表不存在。比如：

     

    2. 位图概念
    所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。 
    1. #pragma once
    2. #include<iostream>
    3. #include<vector>
    4. namespace MySTL
    5. {
    6. 	template<size_t N>
    7. 	class bitset
    8. 	{
    9. 	public:
    10. 		bitset()
    11. 		{
    12. 			_bits.resize(N / 8 + 1, 0);
    13. 		}
    14. 		void set(size_t X)
    15. 		{
    16. 			size_t i = X / 8;
    17. 			size_t j = X % 8;
    18. 			_bits[i] |= (1 << j);
    19. 		}
    20. 		void unset(size_t X)
    21. 		{
    22. 			size_t i = X / 8;
    23. 			size_t j = X % 8;
    24. 			_bits[i] &= (~(1 << j));
    25. 		}
    26. 		bool test(size_t X)
    27. 		{
    28. 			size_t i = X / 8;
    29. 			size_t j = X % 8;
    30. 			return _bits[i] & (1 << j);
    31. 		}
    32. 	private:
    33. 		std::vector<char> _bits;
    34. 	};
    35.  
    36.  
    37.  
    38. 	void test_bitset()
    39. 	{
    40. 		/*bitset<100> bs;
    41. 		int array[] = { 1,2,3,4,5,6,7,8,99,78 };
    42. 		for (const auto& e : array)
    43. 		{
    44. 			bs.set(e);
    45. 		}
    46. 		std::cout<<bs.test(2)<<std::endl;
    47. 		std::cout<<bs.test(99)<<std::endl;
    48. 		std::cout<<bs.test(78)<<std::endl;
    49. 		std::cout<<bs.test(4)<<std::endl;
    51. 		bs.unset(2);
    52. 		bs.unset(99);
    53. 		bs.unset(78);
    54. 		bs.unset(4);
    56. 		std::cout << bs.test(2) << std::endl;
    57. 		std::cout << bs.test(99) << std::endl;
    58. 		std::cout << bs.test(78) << std::endl;
    59. 		std::cout << bs.test(4) << std::endl;*/
    60. 		bitset<-1> bs;
    61. 	}
    62.  
    63. 	
    64.  
    65.  
    66. }

    位图应用

    1. 给定 100 亿个整数，设计算法找到只出现一次的整数？
    2. 给两个文件，分别有 100 亿个整数，我们只有 1G 内存，如何找到两个文件交集？
    3. 位图应用变形： 1 个文件有 100 亿个 int ， 1G 内存，设计算法找到出现次数不超过 2 次的所有整数

    问题1：用两个位图，两个位图可以为00 01 10 

     当一个数第一个位图为0，第二个位图为1，则表明该数只出现一次。

    1. template<size_t N>
    2. 	class TwoBitSet
    3. 	{
    4. 	public:
    5. 		void set(size_t x)
    6. 		{
    7. 			if (_bs1.test(x) == false && _bs2.test(x) == false)  //00 -> 01
    8. 			{
    9. 				_bs2.set(x);
    10. 			}
    11. 			else if (_bs1.test(x) == false && _bs2.test(x))   //01  -> 10
    12. 			{
    13. 				_bs1.set(x);
    14. 				_bs2.unset(x);
    15. 			}
    16. 		}
    17. 		void PrintNumOnce()
    18. 		{
    19. 			for (size_t i = 0; i < N; ++i)
    20. 			{
    21. 				if (!_bs1.test(i) && _bs2.test(i))
    22. 				{
    23. 					std::cout << i << std::endl;
    24. 				}
    25. 			}
    26. 		}
    27. 	private:
    28. 		bitset<N> _bs1;
    29. 		bitset<N> _bs2;
    30. 	};
    31.  
    32. 	void TwoBitSetTest()
    33. 	{
    34. 		int array[] = { 1,1,2,3,4,5,6,6,7,7,8,8,8,9,9,9,9 };
    35. 		TwoBitSet<100> bs;
    36. 		for (const auto& e : array)
    37. 		{
    38. 			bs.set(e);
    39. 		}
    40. 		bs.PrintNumOnce();
    41. 	}
    42. }

     

     

    问题2：

    思路一：一个文件中的整数，set到一个位图，读取第二个文件中的整数判断在不在位图，在就是交集，不在就不是交集。

    1. void TestFindTest()
    2. 	{
    3. 		int array1[] = { 1,5,99,6,6,7,10 };
    4. 		int array2[] = { 1,8,9,6,7,30,10,40,10,40};
    5. 		bitset<100> bs;
    6. 		for (const auto e : array1)
    7. 		{
    8. 			bs.set(e);
    9. 		}
    10. 		for (const auto e : array2)
    11. 		{
    12. 			if (bs.test(e))
    13. 			{
    14. 				std::cout << e << std::endl;
    15. 			}
    16. 		}
    17. 	}

     但是该方法有缺陷：就是第一个文件中的数重复的数会被找出来，还需要去重。

    思路二：

    一个文件的整数，set到一个位图bs1,另一个文件的整数,set到bs2.

      a.遍历bs2中的值，看在不在bs1中，在就是交集。

    1. void TestFindTest()
    2. 	{
    3. 		int array1[] = { 1,5,99,6,6,7,10 };
    4. 		int array2[] = { 1,8,9,6,7,30,10,40,10,40 };
    5. 		bitset<100> bs1;
    6. 		bitset<100> bs2;
    7. 		for (const auto e : array1)
    8. 		{
    9. 			bs1.set(e);
    10. 		}
    11. 		for (const auto e : array2)
    12. 		{
    13. 			bs2.set(e);
    14. 		}
    15.  
    16. 		for (size_t i = 0; i < 100; ++i)
    17. 		{
    18. 			if (bs1.test(i) && bs2.test(i))
    19. 			{
    20. 				std::cout << i << std::endl;
    21. 			}
    22. 		}
    23. 	}

     b.两个位图想与，与完是1的位置的值，就是交集。

    问题3：

    出现1次 00

    出现2次 01

    出现3次 10

    出现4次 11

    1.  
    2. 	template<size_t N>
    3. 	class TwoBitSet
    4. 	{
    5. 	public:
    6. 		void set(size_t x)
    7. 		{
    8. 			if (_bs1.test(x) == false && _bs2.test(x) == false)  //00 -> 01
    9. 			{
    10. 				_bs2.set(x);
    11. 			}
    12. 			else if (_bs1.test(x) == false && _bs2.test(x))   //01  -> 10
    13. 			{
    14. 				_bs1.set(x);
    15. 				_bs2.unset(x);
    16. 			}
    17. 			else if (_bs1.test(x) && _bs2.test(x) == false)   // 10 -> 11
    18. 			{
    19. 				_bs1.set(x);
    20. 				_bs2.set(x);
    21. 			}
    22. 		}
    23. 		void PrintNumOnce()
    24. 		{
    25. 			for (size_t i = 0; i < N; ++i)
    26. 			{
    27. 				if (_bs1.test(i))
    28. 				{
    29. 					std::cout << i << std::endl;
    30. 				}
    31. 			}
    32. 		}
    33. 	private:
    34. 		bitset<N> _bs1;
    35. 		bitset<N> _bs2;
    36. 	};
    37.  
    38. 	void TwoBitSetTest()
    39. 	{
    40. 		int array[] = { 1,1,2,3,4,5,6,6,7,7,8,8,8,9,9,9,9 };
    41. 		TwoBitSet<100> bs;
    42. 		for (const auto& e : array)
    43. 		{
    44. 			bs.set(e);
    45. 		}
    46. 		bs.PrintNumOnce();
    47. 	}

     

  • 相关阅读:
    PostgreSQL的学习心得和知识总结（一百三十九）|深入理解PostgreSQL数据库GUC参数 allow_alter_system 的使用和原理
    Django序列化与反序列化
    走得通，看得见！你的交通“好帮手”
    享元模式
    RH850 G3KH异常处理简述
    硅-罗丹明-二苯并环辛炔；硅基罗丹明-二苯并环辛炔染料,SIR-DBCO，CAS号：2259859-41-9
    harbor的安装及使用
    DW学生美食网页设计作业——餐饮美食汉堡企业网站6页面带轮播(HTML+CSS+JavaScript)
    IntelliJ IDEA + spring-boot+mysql简单实现获取数据库数据接口例子
    正则验证用户名和跨域postmessage
  • 原文地址：https://blog.csdn.net/qq_57283958/article/details/125441673