Mündəricat
Problem bəyanat
Yuxarıdakı K tez-tez verilən elementlərdə array nums [], k ən çox meydana gələn elementləri tapın.
Nümunələr
nums[] = {1, 1, 1, 2, 2, 3}
k = 2
1 2
nums[] = {1}
k = 1
1
Top K Tez-tez Elementlər üçün sadəlövh yanaşma
- Qurmaq a xəritə verilmiş massivdə keçərək element və tezlik.
- Xəritənin girişlərini azalan tezlik sırasına görə sıralayın.
- Sıralanmış xəritənin ilk k elementləri cavaba kömək edir.
misal
nums [] = {1, 1, 2, 3, 3, 3, 4} və k = 2
Elementlərin və tezliyin xəritəsini yaradın
xəritə = {(1, 2), (2, 1), (3, 3), (4, 1)}
Xəritəni azalan tezlik ilə sıralayın
sıralanmış xəritə = {(3, 3), (1, 2), (2, 1), (4, 1)}
İlk k qeydləri cavaba kömək edir
ans = 3 1
Kodu
Top K Tez-tez Elementlər üçün Java Kodu
import java.util.*;
class TopKFrequentElements {
private static void printKFrequent(int[] nums, int k) {
// Length of nums array
int n = nums.length;
// Build the map from nums array
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
} else {
map.put(nums[i], 1);
}
}
// Sort the map, according to decreasing order of frequency and store in a set
TreeSet<Element> set = new TreeSet<>(new Comparator<Element>() {
@Override
public int compare(Element o1, Element o2) {
return Integer.compare(o2.freq, o1.freq);
}
});
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
Element curr = new Element(entry.getKey(), entry.getValue());
set.add(curr);
}
// First k elements of the sorted map contributes to the answer
int index = 0;
for (Element element : set) {
System.out.print(element.value + " ");
index++;
if (index == k)
break;
}
System.out.println();
}
public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 1, 1, 2, 2, 3};
int k = 2;
printKFrequent(nums, k);
// Example 2
nums = new int[]{1};
k = 1;
printKFrequent(nums, k);
}
// class representing a element and value pair
static class Element {
int value;
int freq;
public Element(int value, int freq) {
this.value = value;
this.freq = freq;
}
}
}
Top K Tez-tez Elementlər üçün C ++ Kodu
#include <bits/stdc++.h>
using namespace std;
// structure representing a element and value pair
struct Element {
int value;
int freq;
Element(int v, int f) {
value = v;
freq = f;
}
};
// Comparator to sort elements according to decreasing order of frequency
struct ElemetComp {
bool operator()(const Element &e1, const Element & e2) {
return (e2.freq < e1.freq);
}
};
void printKFrequent(int *nums, int k, int n) {
// Build the map from nums array
unordered_map<int, int> map;
for (int i = 0; i < n; i++) {
if (map.find(nums[i]) == map.end()) {
map.insert(make_pair(nums[i], 1));
} else {
map[nums[i]] = map.find(nums[i])->second + 1;
}
}
// Sort the map, according to decreasing order of frequency and store in a set
set<Element, ElemetComp> set;
unordered_map<int, int>:: iterator itr;
for (itr = map.begin(); itr != map.end(); itr++) {
Element curr(itr->first, itr->second);
set.insert(curr);
}
// First k elements of the sorted map contributes to the answer
int index = 0;
for (auto it = set.begin(); it != set.end(); it++) {
cout<<it->value<<" ";
index++;
if (index == k)
break;
}
cout<<endl;
}
int main() {
// Example 1
int nums[] = {1, 1, 1, 2, 2, 3};
int k = 2;
printKFrequent(nums, k, 6);
// Example 2
int nums2 = {1};
k = 1;
printKFrequent(nums, k, 1);
return 0;
}
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi
O (N * log (N)), bir xəritədən istifadə etdiyimizə görə. Və xəritə elementlərin yerləşdirilməsi üçün N günlük qeydini aparır.
Kosmik Mürəkkəblik
O (N), burada elementləri bu boşluğa cavabdeh olan xəritəyə əlavə edirik. N elementi daxil etdiyimiz üçün kosmik mürəkkəblik də O (N) -dir. Burada N fərqli elementlərin sayını göstərir. Ən pis vəziyyətdə bütün rəqəmlər fərqli ola bilər.
Top K Tez-tez Elementlər üçün optimal yanaşma
Daha yaxşı bir yanaşma, elementə və frekansa maksimum bir yığın etmək, tezliyə görə, yığın üst hissəsini k dəfə çıxarmaq cavab verir.
- Qurmaq a xəritə verilmiş massivdə keçərək element və tezlik.
- Qurmaq a maksimum yığın xəritədən tezliyə görə.
- Yığın üst hissəsini k dəfə çıxarın və bu cavabdır.
Top K Tez-tez Elementlər Kodu
Java kodu
import java.util.*;
class TopKFrequentElements {
private static void printKFrequent(int[] nums, int k) {
// Length of nums array
int n = nums.length;
// Build the map from nums array
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
if (map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
} else {
map.put(nums[i], 1);
}
}
// Construct a max heap of element and frequency according to frequency
PriorityQueue<Element> heap = new PriorityQueue<>(new Comparator<Element>() {
@Override
public int compare(Element o1, Element o2) {
return Integer.compare(o2.freq, o1.freq);
}
});
// Build heap
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
heap.add(new Element(entry.getKey(), entry.getValue()));
}
// First k elements of heap contributes to the answer
for (int i = 0; i < k; i++) {
System.out.print(heap.poll().value + " ");
}
System.out.println();
}
public static void main(String[] args) {
// Example 1
int nums[] = new int[]{1, 1, 1, 2, 2, 3};
int k = 2;
printKFrequent(nums, k);
// Example 2
nums = new int[]{1};
k = 1;
printKFrequent(nums, k);
}
// class representing a element and value pair
static class Element {
int value;
int freq;
public Element(int value, int freq) {
this.value = value;
this.freq = freq;
}
}
}
C ++ kodu
#include <bits/stdc++.h>
using namespace std;
// structure representing a element and value pair
struct Element {
int value;
int freq;
Element(int v, int f) {
value = v;
freq = f;
}
};
// Comparator to sort elements according to decreasing order of frequency
struct ElementComp {
bool operator()(const Element &e1, const Element & e2) {
return (e1.freq < e2.freq);
}
};
void printKFrequent(int *nums, int k, int n) {
// Build the map from nums array
unordered_map<int, int> map;
for (int i = 0; i < n; i++) {
if (map.find(nums[i]) == map.end()) {
map.insert(make_pair(nums[i], 1));
} else {
map[nums[i]] = map.find(nums[i])->second + 1;
}
}
// Construct a max heap of element and frequency according to frequency
priority_queue<Element, vector<Element>, ElementComp> heap;
for (auto itr = map.begin(); itr != map.end(); itr++) {
Element element(itr->first, itr->second);
heap.push(element);
}
// First k elements of heap contributes to the answer
for (int i = 0; i < k; i++) {
Element curr = heap.top();
heap.pop();
cout<<curr.value<<" ";
}
cout<<endl;
}
int main() {
// Example 1
int nums[] = {1, 1, 1, 2, 2, 3};
int k = 2;
printKFrequent(nums, k, 6);
// Example 2
int nums2 = {1};
k = 1;
printKFrequent(nums, k, 1);
return 0;
}
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi
O (k log N + N), burada N elementlərin sayıdır. Çünki ən pis vəziyyətdə girişdəki rəqəmlərin hamısı fərqli ola bilər.
O (log N) faktoru, elementi maksimum yığma və ya üstünlük növbəsinə əlavə etmək vaxtı səbəbindən gəlir.
Kosmik Mürəkkəblik
O (N), çünki N element ionunu ən pis vəziyyətdə saxlayırıq. Məkan mürəkkəbliyi xətti xarakter daşıyır.
