Зөвхөн унших массив дахь олон давтагдах элементүүдийн аль нэгийг нь ол


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг Капитал Нэг Facebook-ийн Google-ийн Үнэндээ Microsoft- Pinterest
Array Хаш

"Зөвхөн унших массив дахь олон давтагдах элементийн аль нэгийг нь олох" гэсэн асуудал нь танд зөвхөн унших эрх олгосон гэж үзжээ. массив хэмжээтэй (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. Мэдүүлэх a газрын зураг.
  8. Холбогдох элементүүдийг шалгахын тулд газрын зураг дээр хөндлөн гулсуулна уу “CurrentBlock”.
    1. Дараа нь [i] arr байрлуулж, газрын зургийн түлхүүрийн утгыг нэмэгдүүлнэ.
    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

Хэрэв хэмжээ нь n + 1 байна дараа нь бид өнгөрөх болно n үүнд. Одоо бид квадрат язгуурыг олох ёстой n үүнийг зарим хувьсагчийн хэл дээр хадгалах хэрэгтэй квадрат язгуур= 2. Одоо бид массивын хүрээг олох ёстой. Бид массив хэллэг үүсгэх гэж байна freqCount 'range = 4' хэмжээтэй бол бид мужийг (n / squareroot) + 1-ээр олох болно.

Бид элементийн давтамжийг траусаар үүсгэсэн массивын хүрээнд тоолно. Бид дайран өнгөрөх бүрдээ freCount [(arr (i) -1) / squareroot] ++ - ийг дагах болно.

Бид freqCount массивдаа дараахь утгуудыг агуулах болно.

freqCount: [2,2,3,0]

Засч байна currentBlock -1-ийн хооронд хэлбэлзэх бөгөөд энэ нь 3. Бид дамжин өнгөрөх болно freqCount массив. Хэрэв бид үүнээс их утгыг олвол квадрат язгуур массивт. Бид freqCount-ийн 2-р индекс дээр currentBlock-ийг i болгож завсарлаж байгааг олж мэдэв. Бид мэдэгдэх болно хэш зураг оролтын массивын элемент бүрийг туулж, элементийн аль нэг нь 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) хэмжээтэй тэнцүү хэсгүүдийн тооцоог хийсэн.