Топ K давтамжтай элементүүд


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Apple-ийн Bloomberg БайтДанс Капитал Нэг Ebay Facebook-ийн Google-ийн Microsoft- Oracle-ийн Халаасны сувд
Array Хаш Хаширч байна Нуруулаг

Асуудлын мэдэгдэл

K давтамжтай элементүүдийн хувьд бид өгөгдсөн болно массив nums [], хамгийн их тохиолддог элементүүдийг ол.

жишээ нь

nums[] = {1, 1, 1, 2, 2, 3}
k = 2
1 2

 

Топ K давтамжтай элементүүд

nums[] = {1}
k = 1
1

Топ K давтамжтай элементүүдийн гэнэн хандлага

  1. Барих газрын зураг өгөгдсөн массиваар туулах замаар элемент ба давтамжийн.
  2. Газрын зургийн оруулгуудыг давтамж буурах дарааллын дагуу эрэмбэл.
  3. Эрэмбэлэгдсэн газрын зургийн эхний k элементүүд хариултанд хувь нэмэр оруулна.

Жишээ нь

nums [] = {1, 1, 2, 3, 3, 3, 4} ба k = 2

Элемент ба давтамжийн газрын зургийг барих
газрын зураг = {(1, 2), (2, 1), (3, 3), (4, 1)}

Газрын зургийг давтамжийн буурах дарааллаар эрэмбэл
эрэмбэлэгдсэн газрын зураг = {(3, 3), (1, 2), (2, 1), (4, 1)}

Эхний k оруулгууд нь хариултанд хувь нэмэр оруулна
ans = 3 1

код

Топ K давтамжтай элементүүдийн Java код

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;
        }
    }
}

Топ K давтамжтай элементүүдийн C ++ код

#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;
}

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N * log (N)), Учир нь бид газрын зургийг ашигласан. Мөн элемент оруулахад газрын зураг N бүртгэлийн цаг хугацаа шаардагдана.

Сансрын нарийн төвөгтэй байдал

O (N), Энд бид энэ зайг хариуцах элементүүдийг газрын зураг руу оруулж байна. Бид N элемент оруулсан тул орон зайн нарийн төвөгтэй байдал нь O (N) болно. Энд N нь ялгаатай элементүүдийн тоог тэмдэглэв. Хамгийн муу тохиолдолд бүх тоо ялгаатай байж болно.

Топ K давтамжтай элементүүдийн оновчтой арга

Илүү сайн арга бол давтамжийн дагуу элемент ба давтамжийг хамгийн их хэмжээгээр хийх явдал юм.

  1. Барих газрын зураг өгөгдсөн массиваар туулах замаар элемент ба давтамжийн.
  2. Барих дээд нуруулдан газрын зураг дээрх давтамжийн дагуу.
  3. Нурууны оройг k удаа арилгаж, энэ нь хариулт болно.

Топ K давтамжтай элементүүдийн код

Java код

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 ++ код

#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;
}

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (k log N + N), энд N нь элементүүдийн тоо юм. Учир нь хамгийн муу тохиолдолд оролтонд байгаа бүх тоонууд ялгаатай байж болно.
O (log N) хүчин зүйл нь хамгийн их овоолго эсвэл тэргүүлэх дараалалд элемент оруулах цаг хугацаатай тул ирдэг.

Сансрын нарийн төвөгтэй байдал

O (N), Учир нь бид N элементийн ионыг хамгийн муу нөхцөлд хадгалж байгаа. Сансрын нарийн төвөгтэй байдал нь шугаман хэлбэртэй байдаг.

Ашигласан материал