加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

判断数组中包含重复数(大数中取重复)

发布时间:2020-12-14 01:40:06 所属栏目:大数据 来源:网络整理
导读:判断数字是否出现在40亿个数中;找出一组数中不重复的数字,即只出现一次的数字;判断一个成员个数为n,成员取值在1 ~ n的数组中是否有重复的成员 问题一 给 40亿个不 重复的unsigned int的整数,没排过序的,然后再给几个数,如何快速判断这几个数是否在那4

判断数字是否出现在40亿个数中;找出一组数中不重复的数字,即只出现一次的数字;判断一个成员个数为n,成员取值在1 ~ n的数组中是否有重复的成员

问题一

40亿个不重复的unsigned int的整数,没排过序的,然后再给几个数,如何快速判断这几个数是否在那40亿个数当中?

算法思路:
unsigned int 的取值范围是0到2^32-1。我们可以申请连续的2^32/8=512M的内存,用每一个bit对应一个unsigned int数字。首先将512M内存都初始化为0,然后每处理一个数字就将其对应的bit设置为1。当需要查询时,直接找到对应bit,看其值是0还是1即可。
其实这个类似的应用是用户在线离线系统,一个用户在线还是离线。

1024B=1KB 1024KB=1MB 1024MB=1GB
2^32B=2^32/1024/1024/1024=4GB

问题二

在2.5亿个整数中找出不重复的整数,内存不足以容纳这2.5亿个整数。
算法思路:
方案一、采用hase的方法,将2.5亿个数拆分成多个小文件,然后取出每个小文件中不重复的数

方案二、采用2-Bitmap(每个数分配2bit,00表示不存在,01表示出现一次,10表示多次,11无意义)进行,共需内存2^32*2bit=1GB内存,还可以接受。然后扫描这2.5亿个整数,查看Bitmap中相对应位,如果是00变01,01变10,10保持不变。所描完事后,查看bitmap,把对应位是01的整数输出即可。

问题三

判断一个成员个数为n,成员取值在1 ~ n的数组中是否有重复的成员

算法思路:
方法1.
对数组进行排序(快速,堆),然后比较相邻的元素是否相同。
时间复杂度为O(nlogn),空间复杂度为O(1)。
方法2、
使用bitmap方法。
定义长度为N/8的char数组,全部初始化为0,每个bit表示对应数字是否出现过。遍历数组,数字出现,将对应bit设置为1,使用 bitmap对数字是否出现进行统计。
时间复杂度为O(n),空间复杂度为O(n)。
方法3、
遍历数组,假设第 i 个位置的数字为 j ,则通过交换将 j 换到下标为 j 的位置上,直到所有数字都出现在自己对应的下标处,或发生了冲突。
时间复杂度为O(n),空间复杂度为O(1)。
方法3示例代码如下:

#include <cstdlib> 
#include <iostream> 
#include <ctime> 
#include <algorithm> 
using namespace std;  
const int MAX = 100;  
bool isDuplicate(int val[])  
{  
    for(int i=0; i<MAX; i++)  
    {  
        if(val[i] != i)  
        {  
            if(val[i] != val[val[i]])  
                swap(val[i],val[val[i]]);  
            else  
                return true;  
        }  
    }  

    return false;  
}  
int main(int argc,char *argv[])  
{  
    int val[MAX];  

    srand((unsigned)time(NULL));  

    cout << "init data: " << endl;  
    for(int i=0; i<MAX; i++)  
    {  
        int temp = rand() % MAX;  
        val[i] = temp;  
        cout << temp << " ";  
    }  
    cout << endl;  

    bool flag = isDuplicate(val);  
    if(flag)  
        cout << "has duplicate elem" << endl;  
    else  
        cout << "no duplicate elem" << endl;  

    system("PAUSE");  
    return EXIT_SUCCESS;  
}

参考:
http://blog.163.com/xychenbaihu@yeah/blog/static/132229655201282054856381/

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读