在2.5億個整數中找出不重復的整數，注，記憶體不足以容納這2.5億個整數。
采用2-Bitmap（每個數分配2bit，00表示不存在，01表示出現一次，10表示多次，11無意義）進行，共需記憶體2^32 * 2 bit=1 GB記憶體，還可以接受。然后掃描這2.5億個整數，查看Bitmap中相對應位，如果是00變01，01變10，10保持不變。所描完事后，查看bitmap，把對應位是01的整數輸出即可。
有大神會解嗎，萬分感謝
uj5u.com熱心網友回復：
應該是先分類,把整數取0-255之后,載入當前分類然后遍歷uj5u.com熱心網友回復：
結構體，位域，結構體陣列，注意變數不要在堆疊上分配。uj5u.com熱心網友回復：
#define N 250000000void fun(unsigned char (*map)[INT_MAX / 4 + 1], int num)
{
int pos = num / 4, offset = 2 * (num % 4);
switch(((*map)[pos] >> offset) & 0x3){
case 0x0:
((*map)[pos] >> offset) |= 0x1;
break;
case 0x1:
((*map)[pos] >> offset) ^= 0x2;
break;
case 0x2:
default:
break;
}
}
int main(){
int src[N] = {0};
unsigned char map[2][INT_MAX / 4 + 1] = "";
int i, j;
for(i = 0; i < N; ++i){
if(src[i] >= 0){
fun(map[0], src[i]);
}else{
fun(map[1], -src[i]);
}
}
printf("Those digits are only showed once in the array : ");
for(j = 0; j < 2; ++j){
for(i = 0; i < INT_MAX + 1; ++i){
if(map[i / 4] >> (2 * (i % 4)) & 0x3 == 0x1){
if(j = 0){
printf("%d, ", i);
}else{
printf("%d, ", -i);
}
}
}
}
printf("\b\b \n");
return 0;
}
uj5u.com熱心網友回復：
#define N 250000000void fun(unsigned char *map, int num)
{
int pos = num / 4, offset = 2 * (num % 4);
switch((map[pos] >> offset) & 0x3){
case 0x0:
map[pos] += 0x1 << offset;
break;
case 0x1:
map[pos] += 0x1 << offset;
break;
case 0x2:
default:
break;
}
}
int main(){
int src[N] = {0};
unsigned char map[2][INT_MAX / 4 + 1] = "";
int i, j;
for(i = 0; i < N; ++i){
if(src[i] >= 0){
fun(map[0], src[i]);
}else{
fun(map[1], -src[i]);
}
}
printf("Those digits are only showed once in the array : ");
for(j = 0; j < 2; ++j){
for(i = 0; i < INT_MAX + 1; ++i){
if((map[i / 4] >> (2 * (i % 4)) & 0x3) == 0x1){
if(j == 0){
printf("%d, ", i);
}else{
printf("%d, ", -i);
}
}
}
}
printf("\b\b \n");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/59016.html
標籤：基礎類