设为首页 加入收藏

TOP

如何从40亿整数中找到不存在的一个(一)
2019-01-02 20:10:45 】 浏览:225
Tags:如何 40亿整数 找到 存在 一个

前言

给定一个最多包含40亿个随机排列的32位的顺序整数的顺序文件,找出一个不在文件中的32位整数。(在文件中至少确实一个这样的数-为什么?)。在具有足够内存的情况下,如何解决该问题?如果有几个外部的“临时”文件可用,但是仅有几百字节的内存,又该如何解决该问题?

分析

这仍然是《编程珠玑》中的一个问题。前面我们曾经提到过《位图法》,我们使用位图法解决了这个问题。32位整型最多有4294967296个整数,而很显然40亿个数中必然会至少缺一个。我们同样也可以尝试使用位图法解决该问题,使用536 870 912个字节,约512M内存存储这40亿整数,存在该整数的位置1,最后遍历比特位,输出第一个比特位为0的位置即可。那如果仅借助几个“临时”文件,使用几百字节的内存的情况下该如何处理呢?

能否使用二分搜索呢?这40亿个整数是随机排列的,因此普通的二分搜索不能找到那个不存在的数。但是我们可以基于二分搜索的思想。

一个整数有32位,我们按照每个比特位是0还是1,将要查找的数据范围一分为二。从最高比特位开始:

  • 将最高比特位为0的放在一堆,为1的放在另外一堆
  • 如果一样多,则随意选择一堆,例如选0,则该位为0
  • 如果不一样多,选择少的一堆继续,如1更少,则该位为1

这里需要做一些解释:

  • 由于2^32个整数中,每一个比特位是1还是0的个数是相同的。如果在这40亿个整数中,某比特位为1和0的个数是相同的,则说明两边都有不存在的数。因此选择任意一堆即可。
  • 如果比特位1的整数比0的整数多,则说明,比特位为0的一堆数中,肯定缺少了一些数。而比特位为1的一堆数中,可能缺少一些数。因此,我们选择少的,也就是比特位为0的那一堆数。
  • 每一次选择,都记录选择的是0还是1,最多32次选择后,便可以至少找到一个整数,不存在这40亿数中。

实例说明

由于32位的整型数据量太多,不便说明,我们用一个4比特的数据对上面的思路再做一个说明。4比特最多有16个数。
假设有以下源数据:


		    
 
			
="hljs">3 5 2 6 7 -1 -4 -6 -3 1 -5

对应二进制形式如下(负数在内存中以补码形式存储):

0011 0101 0010 0110 0111 1111 1100 1010 1101 0001 1011

1.处理第1比特位被分为两部分数据,分别为:

  • 比特位为0的
0011 0101 0010 0110 0111 0001 
  • 比特位为1的
1111 1100 1010 1101 1011

可以看到,第一比特位为1的数为5个,比比特位为0的数要少,因此选择比特位为1的数,继续处理。且第一比特位,获得1.

3.处理第2比特位仍然分为两部分数据,分别为:

  • 比特位为0的
1010 1011
  • 比特位为1的
1111 1100  1101 

可以看到,第一比特位为1的数为3个,比比特位为0的数要多,因此选择比特位为0的数,继续处理。且第二比特位,获得0

2.处理第3比特位仍然被分为两部分数据,分别为:

  • 比特位为0的

  • 比特位为1的
1010 1011

明显看到第三比特位为0的数没有,因此选择比特位0,获得0。至此,已经没有必要继续查找了。

我们最终得到了前三个比特位100,因此不存在于这些数中至少有1000,1001,即-8,-7。

代码实现

C语言实现:

//binarySearch.c
#include <stdio.h>
#include <stdlib.h>

#define MAX_STR 10
#define SOURCE_FILE "source.txt" //最原始文件,需要保留
#define SRC_FILE "src.txt"       //需要分类的文件
#define BIT_1_FILE "bit1.txt"
#define BIT_0_FILE "bit0.txt"
#define INT_BIT_NUM  32
/*
FILE *src   源数据文件指针
FILE *fpBit1 存储要处理的比特位为1的数据
FILE *fpBit0 存储要处理的比特位为0的数据
int bit     要处理的比特位
返回值
0:选择比特位为0的数据继续处理
1:选择比特位为1的数据继续处理
-1:出错
*/
int splitByBit(FILE *src,FILE *fpBit1,FILE *fpBit0,int bit,int *nums)
{
    /*入参检查*/
    if(NULL == src || NULL == fpBit1 || NULL == fpBit0 || NULL == nums)
    {
        printf("input para is NULL");
        return -1;
    }
    /*bit位检查*/
    if(bit < 0 || bit > INT_BIT_NUM )
    {
        printf("the bit is wrong");
        return 
编程开发网
首页 上一页 1 2 3 4 5 下一页 尾页 1/5/5
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇创建第一次C语言程序 下一篇1011 A+B 和 C

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }