74 使用BitSet输出数组中的重复元素

时间:2023-01-17 20:08:02

【本文链接】

http://www.cnblogs.com/hellogiser/p/using-bitset-to-print-duplicate-elements-of-array.html

【题目】

  一个数组有L个元素,取值范围为0到N,其中N<32000,但是不知道N的确切大小。L个元素中有若干个重复元素,只有4KB的内存,如何输出重复元素?

【分析】

  由于数组的取值在一个范围range[1,32000)之间,我们很自然想到用Bitset来处理。使用Bitset,那么1个整数可以使用1个Bit来表示。1byte能够表示8个不同的整数,4kb能够表示32kb个不同整数。因为32kb=32*1024>32000,那么4kb的内存足够表示32000个不同数字。核心在于Bitset中1个整数的存取。开辟一个能够存储N/32+1个int数字的数组,那么对于数字x存储在array[x/32]这个整数的第x%32个bit位。

  即令i=x/32,j=x%32, array[i] |= (1<<j)

  等价于i=x>>5,j=x&(0x1F)

【代码】

 C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
 
// 74_Bitset.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream"
#include <ctime>
#include <algorithm>
using namespace std;

class BitSet
{
public:
    BitSet (int range)
    {
        // [0,range)
        m_nRange = range;
        m_nLength = m_nRange / ;

bitset = new int[m_nLength];
        // init all with 0
; i < m_nLength; i++)
        {
            bitset[i] = ;
        }
    }

~BitSet()
    {
        delete []bitset;
    }

void Set(int number)
    {
        ;
        ;
        bitset[i] |= ( << j);
    }
    bool Get(int number)
    {
        ;
        ;
        ;
    }

void Output()
    {
        ; i < m_nRange; i++)
        {
            if (Get(i))
            {
                cout << i << " ";
            }
        }
        cout << endl;
    }
private:
    int *bitset;
    int m_nRange; // range of numbers
    int m_nLength; // len of array
};

void print(int *a, int n)
{
    ; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}

void PrintDuplicateNumbers(int *a, int n, int count)
{
    cout << "Array numbers======================\n";
    print(a, n);
    cout << "Duplicate numbers======================\n";
    BitSet bs(count);
    ; i < n; i++)
    {
        if (bs.Get(a[i]))
            cout << a[i] << " ";
        else
            bs.Set(a[i]);
    }
    cout << endl;
    cout << "Existing numbers======================\n";
    bs.Output();
}

void test_defualt()
{
    ;
    ;

srand((unsigned int)time(NULL));
    int a[n];
    ; i < n; i++)
    {
        a[i] = rand() % range;
    }
    PrintDuplicateNumbers(a, n, range);
}

int _tmain(int argc, _TCHAR *argv[])
{
    test_defualt();
    ;
}
/*
Array numbers======================
7 0 2 8 0 3 0 3 2 1 7 5 11 5 4 11 1 0 2 4
Duplicate numbers======================
0 0 3 2 7 5 11 1 0 2 4
Existing numbers======================
0 1 2 3 4 5 7 8 11
*/

【本文链接】

http://www.cnblogs.com/hellogiser/p/using-bitset-to-print-duplicate-elements-of-array.html

74 使用BitSet输出数组中的重复元素的更多相关文章

  1. Java-Runoob-高级教程-实例-数组:10&period; Java 实例 – 查找数组中的重复元素-un

    ylbtech-Java-Runoob-高级教程-实例-数组:10. Java 实例 – 查找数组中的重复元素 1.返回顶部 1. Java 实例 - 查找数组中的重复元素  Java 实例 以下实例 ...

  2. 去掉有序数组中的重复元素 c&sol;c&plus;&plus;

    去掉有序数组中的重复元素: int RemoveDuplates(int A[], int nCnt) { ; ; , j = ; i < nCnt && j < nCnt ...

  3. 【leetcode-82,83,26,80】 删除排序链表&sol;数组中的重复元素

    83. 删除排序链表中的重复元素 (1 pass) 给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次. 示例 1: 输入: 1->1->2 输出: 1->2 示例 2: ...

  4. LeetCode&num;26 &vert; Remove Duplicates from Sorted Array 删除有序数组中的重复元素

    一.题目 Description Given a sorted array, remove the duplicates in-place such that each element appear ...

  5. 获取JS数组中所有重复元素

    //获取数组内所有重复元素,并以数组返回 //例:入参数组['1','2','4','7','1','2','2'] 返回数组:['1','2'] function GetRepeatFwxmmc(a ...

  6. 26&period; Remove Duplicates from Sorted Array&lpar;删除排序数组中的重复元素,利用排序的特性,比较大小&rpar;

      Given a sorted array, remove the duplicates in-place such that each element appear only once and r ...

  7. 计蒜客--移除数组中的重复元素 (set)

    给定一个升序排列的数组,去掉重复的数,并输出新的数组的长度. 例如:数组 A = \{1, 1, 2\}A={1,1,2},你的程序应该输出 22 即新数组的长度,新数组为 \{1, 2\}{1,2} ...

  8. JSK 11&colon; 移除数组中的重复元素

    题目描述 给定一个升序排列的数组,去掉重复的数,并输出新的数组的长度. 例如:数组 $A = \{1, 1, 2\}$,你的程序应该输出 $2$ 即新数组的长度,新数组为 $\{1, 2\}$. 要求 ...

  9. 010-PHP输出数组中第某个元素

    <?php $monthName = array(1 => "January", "February", "March",//初 ...

随机推荐

  1. C语言数组删除增加一个元素

    malloc,realloc,calloc一直很头疼,这次笔试题需要在数组后重新分配新的空间的代码是: //删除函数,删除ptr中的ptr[in]元素,n是数组原来的长度. void rmv(int ...

  2. 关于Tcp,为什么一定要进行三次握手呢?

    主要是防止已经失效的请求报文段突然又传送到了服务端而产生的连接的误判. 考虑如下的情况:客户端发送了一个连接请求报文段到服务端,但是在某些网络节点上长时间滞留了,而后客户端又超时重发了一个连接请求报文 ...

  3. leetcode 101

    101. Symmetric Tree Given a binary tree, check whether it is a mirror of itself (ie, symmetric aroun ...

  4. SQL学习备忘

    1.按照拼音首字母的正序或倒序排序 SELECT CREATOR_REALNAME FROM tableName ORDER BY NLSSORT(CREATOR_REALNAME, 'NLS_SOR ...

  5. Linux&sol;Ubuntu常用快捷键

    问题描述:         Linux/Ubuntu常用快捷键   问题解决: +++++++++++++++++++ 全局系统 +++++++++++++++++++++ Alt + F1:相当于w ...

  6. 深入探索C&plus;&plus;对象模型-1

    概述 在实际生产中,遇到一个复杂的类,如果能看出这个类的内存模型结构,那么以后的操作基本就没有难度的: 所以说,学会分析一个类的内存模型,是每一个C++程序员必须要会的知识. 下面,就让我们来了解C+ ...

  7. 03 整合IDEA&plus;Maven&plus;SSM框架的高并发的商品秒杀项目之web层

    Github:https://github.com/nnngu 项目源代码:https://github.com/nnngu/nguSeckill 前端交互流程设计 对于一个系统,需要产品经理.前端工 ...

  8. Android端生成META-INF信息文件的Gradle插件 RapidMetaInfPlugin

    来源博客:Wang Jie's Blog 本文链接:<http://blog.wangjiegulu.com/2018/02/05/Android端生成META-INF信息文件的Gradle插件 ...

  9. JavaWeb-BeginTomcat

    上手Tomcat 1.Ubuntu 18.04 下载/安装Tomcat 以下内容参考链接 安装JDK sudo apt-get update sudo apt-get install default- ...

  10. &lpar;2&rpar;Microsoft office Word 2013版本操作入门&lowbar;快速选中

    1.快速选中一行 .一段文字: 1.1光标在一行内,双击会选中一个词组.快速点击三下会选中一段, 1.2 鼠标移动到行首,单击击会选中一行,双击选中一段. 1.3 选择全部内容 Ctrl+A  , 1 ...