Знайдзіце любы з некалькіх паўтаральных элементаў у масіве толькі для чытання


Узровень складанасці Жорсткі
Часта пытаюцца ў Capital One facebook Google Сапраўды Microsoft Pinterest
масіў гашыш

праблема "Знайсці любы з некалькіх паўтаральных элементаў у масіве толькі для чытання" сцвярджае, што вы мяркуеце, што вам дадзена толькі для чытання масіў памеру (n + 1). Масіў змяшчае цэлыя лікі ад 1 да n. Ваша задача - высветліць любы з паўтараемых элементаў у масіве толькі для чытання.

Прыклад

Знайдзіце любы з некалькіх паўтаральных элементаў у масіве толькі для чытання

n = 5
arr[] = [1,2,4,2,3,5]
2

Тлумачэнне

Гэта адзіны паўторны элемент у масіве толькі для чытання.

n = 9
arr[] = [1,2,4,6,3,5,7,8,9,9]
9

Тлумачэнне

Гэта адзіны паўторны элемент у масіве толькі для чытання.

Алгарытм

  1. Усталёўка "Квадратны корань" да sqrt (n).
  2. Усталюйце дыяпазон (n / squareroot) + 1.
  3. Стварыце масіў дыяпазону памераў.
  4. Падлічыце і захавайце частату кожнага элемента з гэтым (freqCount [(arr [i] - 1) / squareroot] ++).
  5. Усталёўка "CurrentBlock" да дыяпазону-1.
  6. Пакуль i <дыяпазон-1.
    1. Калі freqCount [i]> squareroot, зрабіце currentBlock = i і перапыніце.
  7. Абвясціце а карта.
  8. Правядзіце па карце, каб праверыць, якія элементы належаць "CurrentBlock".
    1. Затым пастаўце arr [i] і павялічце значэнне значэння ключа карты.
    2. Калі значэнне ключа знойдзена больш за 1, тады вяртаецца arr [i].
  9. Іншае вяртанне -1 (элемент не знойдзены).

Тлумачэнне

Мы задалі пытанне, каб даведацца паўторны элемент, які прысутнічае ў масіве, у якім усе цэлыя лікі вар'іруюцца ад 1 да n, а памер масіва складае n + 1. Паколькі ён паказвае наяўнасць аднаго паўторнага элемента, таму і мае памер n + 1.

Простае рашэнне - стварыць HashMap і весці падлік частоты кожнага з элементаў. Але гэта рашэнне патрабуе O (N) часу і O (N) прасторы. Ці можам мы зрабіць гэта лепш?

Мы можам выкарыстоўваць падыход, аналагічны падыходу да раскладання квадратных каранёў. Такі падыход знізіць нашу касмічную складанасць да O (sqrt (N)). Мы ствараем масіў памерам sqrt (N) + 1. І працягваем павялічваць індэксы, якія адпавядаюць значэнням у адпаведнасці з формулай arr (i-1) / sqrt (n). Зрабіўшы гэта, мы напэўна знойдзем індэкс, які мае частату большую за sqrt (N). Зараз мы будзем выкарыстоўваць папярэдні метад, але толькі для элементаў, якія належаць да гэтага дыяпазону.

хэшавання і некаторыя асноўныя матэматыкі выкарыстоўваюцца ў рашэнні задачы. Каб даведацца паўтараемы элемент, мы перададзім масіў і значэнне на 1 менш памеру масіва. Возьмем прыклад для вырашэння гэтай праблемы:

Масіў [] = {6, 1, 2, 3, 5, 4, 6}, n = 6

Калі памер п + 1 тады мы пройдзем n да яго. Цяпер нам трэба высветліць квадратны корань з n і захавайце яго ў нейкай зменнай скажам квадратны корань= 2. Цяпер мы павінны высветліць дыяпазон масіва. Мы збіраемся стварыць масіў say freqCount памеру 'дыяпазон = 4', мы знойдзем дыяпазон па (n / squareroot) + 1.

Мы будзем падлічваць частаты кожнага элемента ў дыяпазоне масіва, які мы стварылі шляхам перамяшчэння. Кожны раз пры пераходзе мы будзем прытрымлівацца freCount [(arr (i) -1) / squareroot] ++.

У выніку мы атрымаем наступныя значэнні ў нашым масіве freqCount.

freqCount: [2,2,3,0]

Налада бягучы блок у дыяпазоне -1, што роўна 3. Мы пройдзем па freqCount масіў. Калі мы знойдзем значэнне большае за квадратны корань у масіве. Мы выяўляем, што пры 2-м індэксе freqCount і ўсталёўваем currentBlock на i і break. Мы аб'явім хэшмап і прайсці кожны элемент уваходнага масіва і праверыць, ці належыць які-небудзь з элементаў currentBlock і sqaureroot, калі так, то мы змяшчаем яго на карту і вяртаем гэтае значэнне arr [i].

Наш выхад будзе: 6

Код C ++ для пошуку любога з некалькіх паўтаральных элементаў у масіве толькі для чытання

#include <unordered_map>
#include<iostream>
#include<math.h>
using namespace std;

int getRepeatedNumber(int arr[], int len)
{
    int squareroot = sqrt(len);
    int range = (len / squareroot) + 1;
    int count[range] = {0};

    for (int i = 0; i <= len; i++)
    {
        count[(arr[i] - 1) / squareroot]++;
    }
    int currentBlock = range - 1;
    for (int i = 0; i < range - 1; i++)
    {
        if (count[i] > squareroot)
        {
            currentBlock = i;
            break;
        }
    }
    unordered_map<int, int> m;
    for (int i = 0; i <= len; i++)
    {
        if ( ((currentBlock * squareroot) < arr[i]) && (arr[i] <= ((currentBlock + 1) * squareroot)))
        {
            m[arr[i]]++;
            if (m[arr[i]] > 1)
                return arr[i];
        }
    }
    return -1;
}
int main()
{
    int arr[] = { 6,1,2, 3, 5, 4, 6 };
    int n = 6;

    cout << "Repeated number(s) in the array is:"<< getRepeatedNumber(arr, n) << endl;
}
Repeated number(s) in the array is:6

Код Java для пошуку любога з некалькіх паўтаральных элементаў у масіве толькі для чытання

import java.util.*;
class arrayRepeatedElements
{
    public static int getRepeatedNumber(int[] arr, int len)
    {
        int squareroot = (int) Math.sqrt(len);
        int range = (len / squareroot) + 1;
        int freqCount[] = new int[range];
        for (int i = 0; i <= len; i++)
        {
            freqCount[(arr[i] - 1) / squareroot]++;
        }
        int currentBlock = range - 1;
        for (int i = 0; i < range - 1; i++)
        {
            if (freqCount[i] > squareroot)
            {
                currentBlock = i;
                break;
            }
        }
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int i = 0; i <= len; i++)
        {
            if ( ((currentBlock * squareroot ) < arr[i]) && ( arr[i] <= ((currentBlock + 1) * squareroot)))
            {
                freq.put(arr[i], 1);
                if (freq.get(arr[i])== 1)
                    return arr[i];
            }
        }
        return -1;
    }
    public static void main(String args[])
    {
        int[] arr = { 6,1, 2, 3, 5, 4, 6 };
        int n = 6;
        System.out.println("Repeated number(s) in the array is:"+getRepeatedNumber(arr, n));
    }
}
Repeated number(s) in the array is:6

Аналіз складанасці

Складанасць часу

O (N) дзе "N" гэта (даўжыня масіва - 1), т. е. n - 1. Паколькі мы павінны прайсці ўсе элементы.

Касмічная складанасць

sqrt (N) дзе "N" гэта (даўжыня масіва - 1), г.зн. n-1. З-за прыроды алгарытму. Спачатку мы зрабілі вылічэнні для раздзелаў, роўных памеру sqrt (N).