career cup 150第五版10.3 中numberOfInts为什么要除以8？# JobHunting - 待字闺中
S*C
1 楼
/**
* 10.3 Given an input file with four billion non-negative integers, provide
an algorithm
to generate an integer which is not contained in the file. Assume you have
1 GB of
memory available for this task.
FOLLOW UP
What if you have only 10 M8 of memory? Assume that all the values are
distinct and
we now have no more than one billion non-negative integers.
CC Page 347
*/
import java.io.*;
import java.util.Scanner;
//A bit array (also known as bitmap, bitset, bit string, or bit vector) is
an array data structure that compactly stores bits.
import java.util.BitSet;//try using this data structure
public class BestSolution {
public static int findMissingNumber(){
long numberOfInts = ((long) Integer.MAX_VALUE) + 1;
System.out.println("numberOfInts / 8 = "+ numberOfInts / 8);//
268435456
BitSet bitSet = new BitSet((int) (numberOfInts / 8));//这里为什么要
除以8？不是说要40亿个bits吗？
FileReader fr = null;
BufferedReader br = null;
Scanner in = null;
try {
fr = new FileReader("D:/data/test2.txt");
br = new BufferedReader(fr);
in = new Scanner(br);
while (in.hasNextInt()) {
bitSet.set(in.nextInt());
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} finally {
try {
if (in != null)
in.close();
if (br != null)
br.close();
if (fr != null)
fr.close();
} catch (IOException e) {
}
}
for (int i = 0; i < numberOfInts; i++)
if (!bitSet.get(i))
return i;
return -1;
}
public static void main(String[] args) throws IOException {
System.out.println("find "+findMissingNumber());
}
}
* 10.3 Given an input file with four billion non-negative integers, provide
an algorithm
to generate an integer which is not contained in the file. Assume you have
1 GB of
memory available for this task.
FOLLOW UP
What if you have only 10 M8 of memory? Assume that all the values are
distinct and
we now have no more than one billion non-negative integers.
CC Page 347
*/
import java.io.*;
import java.util.Scanner;
//A bit array (also known as bitmap, bitset, bit string, or bit vector) is
an array data structure that compactly stores bits.
import java.util.BitSet;//try using this data structure
public class BestSolution {
public static int findMissingNumber(){
long numberOfInts = ((long) Integer.MAX_VALUE) + 1;
System.out.println("numberOfInts / 8 = "+ numberOfInts / 8);//
268435456
BitSet bitSet = new BitSet((int) (numberOfInts / 8));//这里为什么要
除以8？不是说要40亿个bits吗？
FileReader fr = null;
BufferedReader br = null;
Scanner in = null;
try {
fr = new FileReader("D:/data/test2.txt");
br = new BufferedReader(fr);
in = new Scanner(br);
while (in.hasNextInt()) {
bitSet.set(in.nextInt());
}
} catch (FileNotFoundException e) {
e.printStackTrace();
} finally {
try {
if (in != null)
in.close();
if (br != null)
br.close();
if (fr != null)
fr.close();
} catch (IOException e) {
}
}
for (int i = 0; i < numberOfInts; i++)
if (!bitSet.get(i))
return i;
return -1;
}
public static void main(String[] args) throws IOException {
System.out.println("find "+findMissingNumber());
}
}