A monotonically increasing array and someone randomly picks a number how do you find that number
Take 1,2,3,4,5,6,7,8,9… Let’s say 100. Jack Bauer took 88 out. How am I supposed to find it quickly?
1. Implementation of loop traversal
I’m thinking of looping over, comparing the next number to see if it’s one more than the previous number, or missing the next value of the current comparison.
It looks like it might solve the problem, but what if I randomly eliminate two of them? So it’s useless and you have to keep adding if else
/ * * *@authorDay and night of wood */
public class ConcurrnetTest {
public static void main(String[] args){
ConcurrnetTest test = new ConcurrnetTest();
Integer[] arr = test.get();
System.out.println(test.findByFor(arr));
// Or directly compare subscripts
System.out.println(test.findByFor02(arr));
}
// find the number
private Integer findByFor(Integer[] arr) {
Integer res = null;
// If 1 or 100 is removed from the header and tail
if(arr[0] != 1) {
return 1;
}
if (arr[arr.length-1] != 100) {
return 100;
}
for (int i = 0; i < arr.length-1; i++) {
// If the latter is not equal to the former +1 then it is removed
if (arr[i]+1! = arr[i+1]) {
res = arr[i]+1;
break; }}return res;
}
// find the number
private Integer findByFor02(Integer[] arr) {
Integer res = null;
// 100 Special treatment is required if it is not detected
if (arr[arr.length-1] != 100) {
return 100;
}
for (int i = 0; i < arr.length; i++) {
// If the subscript +1 does not correspond to the following table element, there is a problem
// 0:1 1:2 2:3....
if(arr[i] ! = (i+1)) {
res = i+1;
break; }}return res;
}
/** * get 1 to 100@return* /
public Integer[] get(){
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= 100; i++) {
if(i ! =88) { list.add(i); }}return list.toArray(new Integer[0]); }}Copy the code
2. The BitSet implementation
You can think of 1 to 100 as ordered monotonically increasing can we write it this way?
We use an array of bits to indicate whether data is present. A bit of 0 means data is not present, and a bit of 1 means data is present
We can then iterate over the ARR and set the corresponding bit (1), and finally iterate over the bit to see if the bit is 0
Pseudo code:
// Why is the default value 0 because the array contains 0 bits
bit[] bits = new bit[101];
// Discard 88 from array 1 to 100
for (int i = 0; i < arr.length; i++) {
// Set the corresponding subscript to 1
bits[arr[i]] = 1;
}
Copy the code
In Java, arrays of bits are hard to implement and we can use one of the bits of an int or a long
Why write it yourself? Didn’t the big guy provide us with wheels?
Others: Java. Util. BitSet
Implementation code:
/ * * *@authorDay and night of wood */
public class ConcurrnetTest02 {
public static void main(String[] args){
ConcurrnetTest02 test = new ConcurrnetTest02();
Integer[] arr = test.get();
// Loop
System.out.println(test.findByBitSet(arr));
}
// find the number
private Integer findByBitSet(Integer[] arr) {
// From 0 to 100
BitSet bitSet = new BitSet(101);
for (int i = 0; i <arr.length ; i++) {
bitSet.set(arr[i]);
}
// Start from 1 to 100 and see which bit is false, which bit has no value
// 1, 100 can be written as parameters or configurations depending on your implementation
for (int i = 1; i <=100 ; i++) {
if(! bitSet.get(i)){returni; }}return null;
}
/** * get 1 to 100@return* /
public Integer[] get(){
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= 100; i++) {
if(i ! =88) { list.add(i); }}return list.toArray(new Integer[0]); }}Copy the code
When you use bitsets, the logic is pretty simple, no matter how many bits you randomly pick up, set get is enough
Here the use of BitSet is simple, the main consideration is this BitSet knowledge point BitSet can also be mass data statistics
3. A quick look at Bitsets
3.1 a
private long[] words;
Copy the code
A type of long marked with an array of longs = 8 bytes = 8*8 bits = 64 can represent 64 numbers
3.2 Constructors
// Specify the default size
public BitSet(int nbits) {
// It can't be a negative number
if (nbits < 0)
throw new NegativeArraySizeException("nbits < 0: " + nbits);
// Initialize the size
initWords(nbits);
// Flag if the user specified the size
sizeIsSticky = true;
}
private void initWords(int nbits) {
// Calculate how many 64s are required, that is, how many longs are required and initialize the database
words = new long[wordIndex(nbits-1) + 1];
}
/** * ADDRESS_BITS_PER_WORD: 6 */
private static int wordIndex(int bitIndex) {
// >> 6 is the same thing as dividing by 64. 2^6=64
return bitIndex >> ADDRESS_BITS_PER_WORD;
}
Copy the code
3.3 set method
Sets the specified value to true
public void set(int bitIndex) {
// Invalid bit position
if (bitIndex < 0)
throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
// Calculate which index bitIndex/64 corresponds to this position in long array
int wordIndex = wordIndex(bitIndex);
// Check whether the system needs to be expanded. If necessary, expand the system directly. By default, the system expands by 2*words
// If wordIndex>2*words.length then expand to wordIndex size
expandTo(wordIndex);
// It is this operation that sets the corresponding position to 1
// 1L << bitIndex converts the bitIndex to the desired bitIndex
// Example: 10 == 10000000000
// If one of them is 1, it is 1
words[wordIndex] |= (1L << bitIndex); // Restores invariants
checkInvariants();
}
Copy the code
3.3 the get method
Returns true if the specified value exists false if it does not
Public Boolean get (int bitIndex) {/ / illegal judgment if (bitIndex < 0) throw new IndexOutOfBoundsException (" bitIndex < 0: " + bitIndex); // Detect something checkInvariants(); Int wordIndex = wordIndex(bitIndex); Return (wordIndex < wordsInUse) && ((words[wordIndex] &(1L << bitIndex)) ! = 0); }Copy the code
3.4 Other Methods
Clear () clears all Settings so bit is false clear(int bitIndex) set subscript to false BitSet get(int fromIndex, Return BitSet set(int bitIndex, Boolean value) Set the specified position true or false set(int fromIndex, Boolean value) Int toIndex set(int fromIndex, int toIndex, Boolean value) Set a range to true or false clear(fromIndex, toIndex); Set to false and specified range (BitSet set) merger BitSet to oneself use & corresponding position for 1 results: is 1 or (BitSet set) merger BitSet to oneself use | as long as there is a corresponding position is 1 the result: Xor (BitSet set) merges the BitSet into the corresponding position, one bit is 1 and one bit is 0. Result: 1 andNot(BitSet set) merges the BitSet into the corresponding position, one bit is 1Copy the code
Welcome to our official account: