Найти дубликаты массива, используя битовый массив

31.12.2019Массивы, Немного магии

У вас есть массив из N чисел, где N не более 32 000. Массив может содержать дубликаты записей, и вы не знаете, что такое N. Если в памяти доступно всего 4 килобайта памяти, как распечатать все дублирующиеся элементы в массиве?

Примеры:

Input : arr[] = {1, 5, 1, 10, 12, 10}
Output : 1 10
1 and 10 appear more than once in given
array.

Input : arr[] = {50, 40, 50}
Output : 50

Спросил в: Amazon

У нас есть 4 килобайта памяти, что означает, что мы можем адресовать до 8 * 4 * 2 ¹⁰ бит. Обратите внимание, что 32 * 2 ¹⁰ битов больше, чем 32000. Мы можем создать бит с 32000 битами, где каждый бит представляет одно целое число.

Примечание: если вам нужно создать бит с более чем 32000 битами, вы можете легко создать больше и более 32000;

Используя этот битовый вектор, мы можем затем выполнить итерацию по массиву, помечая каждый элемент v, устанавливая бит v в 1. Когда мы сталкиваемся с дублирующим элементом, мы печатаем его.

Ниже приведена реализация идеи.

C ++

// C ++ программа для печати всех дубликатов в массиве
#include <bits/stdc++.h>

using namespace std;

// Класс для представления массива битов
// массив целых

class BitArray

{

int *arr;

public:

BitArray() {}

// Конструктор

BitArray(int n)

{

// Делим на 32. Чтобы сохранить n бит, нам нужно

// n / 32 + 1 целое число (при условии, что int хранится

// используя 32 бита)

arr = new int[(n >> 5) + 1];

}

// Получить значение бита в заданной позиции

bool get(int pos)

{

// Делим на 32, чтобы найти позицию

// целое число

int index = (pos >> 5);

// Теперь найти номер бита в arr [index]

int bitNo = (pos & 0x1F);

// Найти значение заданного номера бита в

// arr [index]

return (arr[index] & (1 << bitNo)) != 0;

}

// Устанавливает бит в заданной позиции

void set(int pos)

{

// Находим индекс позиции бита

int index = (pos >> 5);

// Установить номер бита в arr [index]

int bitNo = (pos & 0x1F);

arr[index] |= (1 << bitNo);

}

// Основная функция для печати всех дубликатов

void checkDuplicates(int arr[], int n)

{

// создать бит с 32000 битами

BitArray ba = BitArray(320000);

// Обход элементов массива

for (int i = 0; i < n; i++)

{

// Индекс в битовом массиве

int num = arr[i];

// Если num уже присутствует в битовом массиве

if (ba.get(num))

cout << num << " ";

// Иначе вставка num

else

ba.set(num);

}

};

// Код драйвера

int main()

{

int arr[] = {1, 5, 1, 10, 12, 10};

int n = sizeof(arr) / sizeof(arr[0]);

BitArray obj = BitArray();

obj.checkDuplicates(arr, n);

return 0;

}

// Этот код предоставлен
// sanjeev2552

Джава

// Java программа для печати всех дубликатов в массиве

import java.util.*;

import java.lang.*;

import java.io.*;

// Класс для представления массива битов
// массив целых

class BitArray

{

int[] arr;

// Конструктор

public BitArray(int n)

{

// Делим на 32. Чтобы сохранить n бит, нам нужно

// n / 32 + 1 целое число (при условии, что int хранится

// используя 32 бита)

arr = new int[(n>>5) + 1];

}

// Получить значение бита в заданной позиции

boolean get(int pos)

{

// Делим на 32, чтобы найти позицию

// целое число

int index = (pos >> 5);

// Теперь найти номер бита в arr [index]

int bitNo = (pos & 0x1F);

// Найти значение заданного номера бита в

// arr [index]

return (arr[index] & (1 << bitNo)) != 0;

}

// Устанавливает бит в заданной позиции

void set(int pos)

{

// Находим индекс позиции бита

int index = (pos >> 5);

// Установить номер бита в arr [index]

int bitNo = (pos & 0x1F);

arr[index] |= (1 << bitNo);

}

// Основная функция для печати всех дубликатов

static void checkDuplicates(int[] arr)

{

// создать бит с 32000 битами

BitArray ba = new BitArray(320000);

// Обход элементов массива

for (int i=0; i<arr.length; i++)

{

// Индекс в битовом массиве

int num = arr[i] - 1;

// Если num уже присутствует в битовом массиве

if (ba.get(num))

System.out.print(num +" ");

// Иначе вставка num

else

ba.set(num);

}

// Код драйвера

public static void main(String[] args) throws

java.lang.Exception

{

int[] arr = {1, 5, 1, 10, 12, 10};

checkDuplicates(arr);

}

python3

# Python3 программа для печати всех дубликатов в массиве

# Класс для представления массива битов с использованием
# массив целых

class BitArray:

# Конструктор

def __init__(self, n):

# Разделите на 32. Чтобы сохранить n бит, нам нужно

# n / 32 + 1 целое число (при условии, что int хранится

# используя 32 бита)

self.arr = [0] * ((n >> 5) + 1)

# Получить значение бита в заданной позиции

def get(self, pos):

# Разделите на 32, чтобы найти положение

# целое число

self.index = pos >> 5

# Теперь найдите номер бита в arr [index]

self.bitNo = pos & 0x1F

# Найти значение заданного номера бита в

# arr [index]

return (self.arr[self.index] &

(1 << self.bitNo)) != 0

# Устанавливает бит в заданной позиции

def set(self, pos):

# Найти индекс позиции бита

self.index = pos >> 5

# Установить номер бита в arr [index]

self.bitNo = pos & 0x1F

self.arr[self.index] |= (1 << self.bitNo)

# Основная функция для печати всех дубликатов

def checkDuplicates(arr):

# создать бит с 32000 битами

ba = BitArray(320000)

# Обход элементов массива

for i in range(len(arr)):

# Индекс в битовом массиве

num = arr[i]

# Если num уже присутствует в битовом массиве

if ba.get(num):

print(num, end = " ")

# Иначе вставить номер

else:

ba.set(num)

Код водителя

if __name__ == "__main__":

arr = [1, 5, 1, 10, 12, 10]

checkDuplicates(arr)

# Этот код предоставлен
# sanjeev2552

C #

// C # программа для печати всех дубликатов в массиве

// Класс для представления массива битов
// массив целых

using System;

class BitArray

{

int[] arr;

// Конструктор

public BitArray(int n)

{

// Делим на 32. Чтобы сохранить n бит, нам нужно

// n / 32 + 1 целое число (при условии, что int хранится

// используя 32 бита)

arr = new int[(int)(n >> 5) + 1];

}

// Получить значение бита в заданной позиции

bool get(int pos)

{

// Делим на 32, чтобы найти позицию

// целое число

int index = (pos >> 5);

// Теперь найти номер бита в arr [index]

int bitNo = (pos & 0x1F);

// Найти значение заданного номера бита в

// arr [index]

return (arr[index] & (1 << bitNo)) != 0;

}

// Устанавливает бит в заданной позиции

void set(int pos)

{

// Находим индекс позиции бита

int index = (pos >> 5);

// Установить номер бита в arr [index]

int bitNo = (pos & 0x1F);

arr[index] |= (1 << bitNo);

}

// Основная функция для печати всех дубликатов

static void checkDuplicates(int[] arr)

{

// создать бит с 32000 битами

BitArray ba = new BitArray(320000);

// Обход элементов массива

for (int i = 0; i < arr.Length; i++)

{

// Индекс в битовом массиве

int num = arr[i];

// Если num уже присутствует в битовом массиве

if (ba.get(num))

Console.Write(num + " ");

// Иначе вставка num

else

ba.set(num);

}

// Код драйвера

public static void Main()

{

int[] arr = {1, 5, 1, 10, 12, 10};

checkDuplicates(arr);

}

// Этот код предоставлен Rajput-Ji

Выход:

1 10

Эта статья предоставлена г-ном Сомешем Авастхи . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти дубликаты массива, используя битовый массив

0.00 (0%) 0 votes