74 使用BitSet輸出數組中的重復元素，bitset數組
【本文鏈接】
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)
【代碼】
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 / 32 + 1;
bitset = new int[m_nLength];
// init all with 0
for (int i = 0; i < m_nLength; i++)
{
bitset[i] = 0;
}
}
~BitSet()
{
delete []bitset;
}
void Set(int number)
{
int i = number / 32;
int j = number % 32;
bitset[i] |= (1 << j);
}
bool Get(int number)
{
int i = number / 32;
int j = number % 32;
return (bitset[i] & (1 << j)) != 0;
}
void Output()
{
for (int i = 0; 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)
{
for (int i = 0; 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);
for (int i = 0; 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()
{
const int n = 20;
const int range = 12;
srand((unsigned int)time(NULL));
int a[n];
for (int i = 0; i < n; i++)
{
a[i] = rand() % range;
}
PrintDuplicateNumbers(a, n, range);
}
int _tmain(int argc, _TCHAR *argv[])
{
test_defualt();
return 0;
}
/*
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
輸出數組中的元素---重復的元素只輸出一次如,a[]={1,4,1,5,2,2,6};則輸出結果應
#include "stdio.h"
main()
{
int i,j,N=7;
int a[] ={1,4,1,5,2,2,6};
printf("%d",a[0]);
for(i=1;i<N;i++) {
for(j=0;j<i;j++) {
if(a[j]==a[i])
break;
if(j==i-1)
printf("%d",a[i]);
}
}
}
哥們兒不好意思，這下調試好了，試一下吧。
在c語言中輸入數組兩個數組，查找重復元素並輸出怎寫
可以一次讀入N個數據。可以考慮以回車結束讀入的一組。
參考如下寫法：
#include "stdio.h"
#define Max 100
int X[Max]={0,},Y[Max]={0,};
int main()
{
int i=0,j=0;
int a,b;
char c=0;
printf("輸入第一個數組(以空格分開，回車結束)");
while((c!='\n'))
scanf("%d%c",X+i++,&c);
c=0;
printf("輸入第二個數組(以空格分開，回車結束)");
while((c!='\n'))
scanf("%d%c",Y+j++,&c);
for(a=0;a<i;a++)
for(b=0;b<j;b++)
if(X[a]==Y[b])
printf("%d \t",X[a]);
return 0;
}
