problem "Yalnız oxunan massivdə təkrarlanan çoxsaylı elementlərdən birini tapın" problemi sizə yalnız oxunuş verildiyini düşünür array ölçüsü (n + 1). Bir sıra 1-dən n-ə qədər olan ədədi ehtiva edir. Task yalnız oxunaqlı massivdə təkrarlanan elementlərdən birini tapmaqdır.
Mündəricat
misal
n = 5 arr[] = [1,2,4,2,3,5]
2
Izahat
Bu, yalnız oxunan massivdəki təkrarlanan elementdir.
n = 9 arr[] = [1,2,4,6,3,5,7,8,9,9]
9
Izahat
Bu, yalnız oxunan massivdəki təkrarlanan elementdir.
Alqoritm
- Set "Kvadrat" sqrt (n) -ə.
- Aralığı (n / kvadrat) + 1 olaraq təyin edin.
- Ölçü aralığında bir sıra yaradın.
- Hər elementin tezliyini bununla sayın və saxlayın (freqCount [(arr [i] - 1) / squareroot] ++).
- Set “CurrentBlock” aralığa-1.
- I <aralığında-1.
- FreqCount [i]> squareroot varsa, currentBlock = i edin və qırın.
- Bəyan edin a xəritə.
- Mənsub olan elementləri yoxlamaq üçün xəritədə keçin “CurrentBlock”.
- Sonra arr [i] qoyun və xəritə düyməsinin dəyərini artırın.
- Açarın dəyəri 1-dən çox olduqda arr [i] -ə qayıdın.
- Else return -1 (element tapılmadı).
Izahat
Bütün ədədlərin 1-dən n-ə qədər olduğu və bir sıra ölçüsünün n + 1 olduğu bir massivdə mövcud olan təkrarlanan elementi tapmaq üçün bir sual verdik. Təkrarlanan bir elementin mövcudluğunu göstərdiyinə görə n + 1 ölçüsünə malikdir.
Sadə həll yolu bir HashMap yaratmaq və elementlərin hər birinin tezlik sayını saxlamaqdır. Ancaq bu həll üçün O (N) vaxt və O (N) məkan tələb olunur. Bundan daha yaxşı iş görə bilərikmi?
Kvadrat kök parçalanmasına bənzər bir yanaşma istifadə edə bilərik. Bu yanaşma kosmik mürəkkəbliyimizi O (sqrt (N)) səviyyəsinə endirəcəkdir. Sqrt (N) + 1 ölçülü bir sıra yaradırıq və arr (i-1) / sqrt (n) düsturuna görə dəyərlərə uyğun indeksləri artırın. Bunu etdikdən sonra mütləq sqrt (N) -dən çox bir tezliyə sahib bir indeks tapacağıq. İndi əvvəlki metodu istifadə edəcəyik, ancaq bu aralığa aid elementlər üçün.
Hashing və problemin həllində bəzi əsas riyaziyyatlardan istifadə olunur. Təkrarlanan elementi tapmaq üçün bir sıra və massivin ölçüsündən 1 az bir dəyər ötürəcəyik. Bunu həll etmək üçün bir nümunə götürək:
Dizi [] = {6, 1, 2, 3, 5, 4, 6}, n = 6
Ölçüdürsə n + 1 o zaman keçəcəyik n buna. İndi kökünün kvadrat kökünü tapmalıyıq n və bəzi dəyişənlərə görə saxla kvadrat= 2. İndi serialın çeşidini öyrənməliyik. Bir sıra deyəcəyik deyəcəyik freqCount 'üçündür = 4' ölçüsündə, aralığını (n / squareroot) + 1 ilə tapacağıq.
Keçərək yaratdığımız sıra aralığında hər bir elementin tezliklərini sayacağıq. Hər dəfə keçdiyimiz zaman freCount [(arr (i) -1) / squareroot] ++.
FreqCount massivimizdə aşağıdakı dəyərlərə sahib olacağıq.
freqHount: [2,2,3,0]
Qurulması cari blok -1 aralığına, yəni 3-ə bərabərdir freqCount massiv. Dəyəri daha böyük tapsaq kvadrat massivdə. FreqCount-un 2-ci indeksində və currentBlock-u i-yə qoyub pozduğunu görürük. Elan edəcəyik hashmap və giriş massivinin hər bir elementini keçin və elementlərdən birinin currentBlock və sqaureroot-a aid olub olmadığını yoxlayın, bəli əgər onu bir xəritəyə qoyub arr [i] dəyərini qaytarırıq.
Çıxışımız olacaq: 6
Yalnız oxunan massivdə birdən çox təkrarlanan elementlərdən birini tapmaq üçün C ++ kodu
#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
Yalnız oxunan massivdə birdən çox təkrarlanan elementlərdən birini tapmaq üçün Java kodu
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
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi
O (N) hara "N" (massivin uzunluğu - 1), yəni n - 1., çünki bütün elementləri keçməliyik.
Kosmik Mürəkkəblik
kvadrat (N) hara "N" (massivin uzunluğu - 1), yəni n-1-dir. Alqoritmin təbiətinə görə. Əvvəlcə sqrt (N) ölçüsünə bərabər hissələr üçün hesablama apardıq.
