იპოვნეთ მრავალი განმეორებადი ელემენტიდან რომელიმე მხოლოდ წაკითხვის მასივში


Რთული ტური Hard
ხშირად ეკითხებიან 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. უცნობია "მიმდინარე ბლოკი" დიაპაზონში -1.
  6. მიუხედავად იმისა, რომ მე <დიაპაზონი -1.
    1. თუ freqCount [i]> squareroot, მაშინ გააკეთე currentBlock = i და გატეხე.
  7. გამოაცხადეთ ა რუკა.
  8. გაიარეთ რუქაზე, რათა შეამოწმოთ ის ელემენტები, რომლებიც ეკუთვნის "მიმდინარე ბლოკი".
    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

თუ ზომაა n + 1 მაშინ ჩვენ გავივლით n მას. ახლა ჩვენ უნდა გავარკვიოთ კვადრატული ფესვი n და შეინახეთ იგი რაიმე ცვლადისთვის კვადრატული ფესვი= 2 ახლა ჩვენ უნდა გავერკვეთ მასივის დიაპაზონში. ჩვენ შევქმნით მასივის სათქმელს freqCount ზომის 'დიაპაზონი = 4', ჩვენ ვიპოვით დიაპაზონს (n / კვადრატული ფუძით) + 1-ით.

ჩვენ დავთვლით თითოეული ელემენტის სიხშირეებს მასივის დიაპაზონში, რომელიც შევქმენით ტრავერსით. ყოველთვის, როდესაც ჩვენ გადავკვეთთ, ჩვენ მივყვებით freCount [(arr (i) -1) / squareroot] ++.

ჩვენ საბოლოოდ გვექნება შემდეგი მნიშვნელობები ჩვენს freqCount მასივში.

freqCount: [2,2,3,0]

შექმნის მიმდინარე ბლოკი დიაპაზონში -1 ეს არის 3. ჩვენ გადავკვეთთ freqCount მასივი თუ ჩვენ აღმოვაჩენთ მნიშვნელობას, ვიდრე კვადრატული ფესვი მასივში. ჩვენ ვხვდებით, რომ freqCount- ის მე -2 ინდექსში და მითითებული currentBlock და i და break. ჩვენ გამოვაცხადებთ ა ჰაშმაპი და გადავკვეთთ შეყვანის მასივის თითოეულ ელემენტს და შეამოწმეთ, რომელიმე ელემენტი ეკუთვნის მიმდინარე ბლოკს და 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) - ის ზომის.