Тек оқуға арналған жиымнан бірнеше қайталанатын элементтердің кез келгенін табыңыз  


Күрделілік дәрежесі қиын
Жиі кіреді Capital One Facebook Google шынында Microsoft Pinterest
Array Hash

«Тек оқуға арналған жиымдағы бірнеше қайталанатын элементтердің кез келгенін табу» мәселесі сізге тек оқуға берілген деп тұжырымдайды массив өлшемі (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 / квадрат) + 1 етіп орнатыңыз.
  3. Өлшем ауқымының жиымын жасаңыз.
  4. Әр элементтің жиілігін осымен санаңыз және сақтаңыз (freqCount [(arr [i] - 1) / squareroot] ++).
  5. жиынтық “CurrentBlock” диапазонға дейін-1.
  6. I <ауқым-1.
    1. Егер freqCount [i]> squareroot болса, онда currentBlock = i жасап, үзіліс жасаңыз.
  7. Декларация а карта.
  8. Тиісті элементтерді тексеру үшін карта арқылы жүріңіз “CurrentBlock”.
    1. Содан кейін [i] массивін қойып, карта кілтінің мәнін арттырыңыз.
    2. Егер кілттің мәні 1-ден үлкен болса, онда [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

Егер өлшемі болса n + 1 содан кейін біз өтеміз n оған. Енді біз квадрат түбірін анықтауымыз керек n және оны белгілі бір айнымалыға дейін сақтаңыз шаршы= 2. Енді біз массивтің ауқымын білуіміз керек. Біз массив құрамыз freqCount 'ауқым = 4' өлшемі, (n / квадрат) + 1 бойынша аралықты табамыз.

Біз әр элементтің жиіліктерін санау арқылы жасаған массив ауқымында санап шығамыз. Біз өткен сайын freCount [(arr (i) -1) / squareroot] ++ ұстанамыз.

Біздің freqCount массивінде келесі мәндер болады.

Сондай-ақ, қараңыз
Массивтен a + b + c = d болатындай етіп d ең үлкенін табыңыз

freqCount: [2,2,3,0]

Орнату ағымдағы блок -1-ге дейін, яғни 3-ті freqCount массив. Егер мәнін үлкеннен тапсақ шаршы массивте. Біз freqCount индексінің 2-інде және 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. Біз барлық элементтерді айналып өтуіміз керек.

Сондай-ақ, қараңыз
Ең ұзақ өсетін дәйектілік

Ғарыштың күрделілігі

квадрат (N) қайда «N» бұл (массивтің ұзындығы - 1), яғни n-1. Алгоритмнің сипатына байланысты. Біріншіден, біз sqrt (N) өлшеміне тең бөлімдер үшін есептеулер жүргіздік.