Рубрики

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

У вас есть массив из 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 10 бит. Обратите внимание, что 32 * 2 10 битов больше, чем 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