عناصر متكررة من أعلى K


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون أجهزة آبل بلومبرغ ByteDance عاصمة واحدة يباي Facebook جوجل Microsoft أوراكل الجواهر الجيب
مجموعة مزيج تجزئة كومة

المشكلة بيان

في عناصر متكررة أعلى K قدمنا مجموعة nums [] ، ابحث عن العناصر الأكثر تكرارا.

أمثلة

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

 

عناصر متكررة من أعلى K

nums[] = {1}
k = 1
1

نهج ساذج للعناصر الأكثر تكرارًا K

  1. بناء رسم خريطة للعنصر والتردد عن طريق اجتياز المصفوفة المحددة.
  2. قم بفرز مدخلات الخريطة وفقًا لترتيب تنازلي للتردد.
  3. تساهم عناصر k الأولى من الخريطة التي تم فرزها في الإجابة.

مثال

الأعداد [] = {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 الأولى في الإجابة
الجواب = 3 1

رمز

كود جافا لأعلى K للعناصر المتكررة

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

كود C ++ لأعلى K للعناصر المتكررة

#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 العناصر المتكررة

أفضل طريقة هي عمل كومة قصوى للعنصر والتردد ، وفقًا للتردد ، وإزالة الجزء العلوي من الكومة k مرة يعطي الإجابة.

  1. بناء رسم خريطة للعنصر والتردد عن طريق اجتياز المصفوفة المحددة.
  2. بناء كومة ماكس حسب التردد من الخريطة.
  3. قم بإزالة الجزء العلوي من الكومة k مرة وهذه هي الإجابة.

رمز لأعلى K للعناصر المتكررة

كود جافا

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 N + N)، هنا N هو عدد العناصر. لأنه في أسوأ الأحوال ، قد تكون جميع الأرقام الموجودة في الإدخال مميزة.
يأتي عامل O (log N) بسبب الوقت اللازم لإدراج عنصر في كومة الذاكرة المؤقتة القصوى أو قائمة انتظار الأولوية.

تعقيد الفضاء

O (N) لأننا نخزن عناصر N أيون أسوأ حالة. تعقيد الفضاء خطي.

المراجع