Find out not to repeat in 250 million integer integer, note, memory is not enough to accommodate the integer 250 million,
2 - Bitmap (each number 2 bit allocation, 00 said does not exist, 01 comes once said, 10 said many times, 11 meaningless), total memory 2 ^ 32 bit * 2=1 GB of memory, also can accept, then scanning the integer 250 million, view the corresponding bit in the Bitmap, if is 00 change 01,01 10, 10 remains the same, the tracing afterward, view Bitmap, the corresponding bit is 01 integer output,
Would have a great spirit solution, thank you very much

CodePudding user response:

Should be classified first, after take a scale of 0-255 integer, then traverse load current classification

CodePudding user response:

Structure, domain and structure arrays, pay attention to the variables are not allocated on the stack,

CodePudding user response:

# define N 250000000

Void fun (unsigned char (* map) [INT_MAX/4 + 1], int num)
{
Int pos=num/4, offset=2 * (num % 4);

The switch (((* map) (pos) & gt;> Offset) & amp; {0 x3)
Case 0 x0:
(map) (* (pos) & gt;> Offset) |=0 x1;
break;
Case 0 x1:
(map) (* (pos) & gt;> Offset) ^=0 x2;
break;
Case 0 x2:
Default:
break;
}
}

Int main () {
Int the SRC [N]={0};
Unsigned char map [2] [INT_MAX/4 + 1)="";

Int I, j;
for(i=0; I & lt; N; + + I) {
If (SRC [I] & gt;=0) {
Fun (map [0], SRC [I]);
} else {
Fun (map [1], the SRC [I]);
}
}

Printf (" Those who are only showed once in the array: ");
for(j=0; J & lt; 2; + + j) {
for(i=0; I & lt; INT_MAX + 1; + + I) {
If (map [4] I/& gt;> (2 * (I % 4)) & amp; {0 x3==0 x1)
If (j=0) {
Printf (" % d, ", I);
} else {
Printf (" % d ", I);
}
}
}
}
Printf (" \ \ b b \ n ");

return 0;
}

CodePudding user response:

# define N 250000000

Void fun (unsigned char * map, int num)
{
Int pos=num/4, offset=2 * (num % 4);

The switch ((map (pos) & gt;> Offset) & amp; {0 x3)
Case 0 x0:
The map (pos) +=0 x1 & lt; break;
Case 0 x1:
The map (pos) +=0 x1 & lt; break;
Case 0 x2:
Default:
break;
}
}

Int main () {
Int the SRC [N]={0};
Unsigned char map [2] [INT_MAX/4 + 1)="";

Int I, j;
for(i=0; I & lt; N; + + I) {
If (SRC [I] & gt;=0) {
Fun (map [0], SRC [I]);
} else {
Fun (map [1], the SRC [I]);
}
}

Printf (" Those who are only showed once in the array: ");
for(j=0; J & lt; 2; + + j) {
for(i=0; I & lt; INT_MAX + 1; + + I) {
If ((map [4] I/& gt;> (2 * (I % 4)) & amp; {0 x3)==0 x1)
If (j==0) {
Printf (" % d, ", I);
} else {
Printf (" % d ", I);
}
}
}
}
Printf (" \ \ b b \ n ");

return 0;
}