Введение в алгоритм больших данных

2.3 removal
Remove and insert operation Similar to:

• 
  Establishment method 1: Directly established Bitmap
  

int n=32*10000;// Number of elements to be expressed
bool* bitmap=new bool[n];// Establish Bitmap directly in place
bitmap[200]=0;// Remove element 200

• 
  1
  
• 
  2
  
• 
  3
  

• 
  Establishment mode 2: Bitmap established in int
  

int* bitmap=new int[10000];// Establish Bitmap with a four-byte int type, which means a 4-byte int element of the int array can represent 32 integers.
bitmap[200/32]=bitmap[200/32] & ~(1<<(200%32));// The opposite of the inserted bit operation is exactly

• 
  1
  
• 
  2
  

2.4 Bit MAP application
Combining the characteristics of Bit Map, you can summarize the following applications:

• 
  Sort
  

For data without repeated numbers, you can store these digitally stored positions, and then traverse the bitmap, the output content of 1 is 1, you can complete the sort of the data. Time, spatial complexity is O (N).
It can be seen that the use of bitmaps themselves have a large speed advantage, especially for large quantities of data. However, a fatal problem is that the input data cannot be repeated. . .

• 
  Look at
  

If you need to find a duplicate data in a set of data, then you should first think of a bitmap:
First, the status of each data is encoded:
00: Ранее не появлялся; 01: Появился; 11 появляется дважды или более. (Состояние каждого 2-го представляет элемент)
Затем, в 2 БИТА, выполняется обход входных данных: Исходное состояние всех элементов равно 00; после вставки элемента в первый раз состояние элемента преобразуется в 01; когда этот элемент вставлен, состояние со второго раза. 01 Преобразуйте 11 и пометьте этот элемент как повторяющийся; когда этот элемент вставлен, состояние сохраняется на уровне 11.

•