אלמנטים תכופים K עליונים


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית תפוח עץ בלומברג Byte קפיטל אחד eBay פייסבוק Google מיקרוסופט אורקל אבני חן כיס
מערך בליל חבטות ערימה

הצהרת בעיה

באלמנטים תכופים K העליונים נתנו מערך מספרים [], מצא את k האלמנטים הנפוצים ביותר.

דוגמאות

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 ראשונים תורמים לתשובה
ans = 3 1

קופונים

קוד Java לאלמנטים תכופים של 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 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 * יומן (N)), כי השתמשנו במפה. והמפה לוקחת זמן יומן N להכנסת אלמנטים.

מורכבות בחלל

O (N) כאן אנו מכניסים את האלמנטים למפה, האחראית על המרחב הזה. מכיוון שהכנסנו אלמנטים N, מורכבות החלל היא גם O (N). כאן N ציין את מספר האלמנטים המובהקים. במקרה הגרוע ביותר, כל המספרים עשויים להיות שונים.

גישה אופטימלית לאלמנטים תכופים K עליונים

גישה טובה יותר היא להכין ערימה מקסימלית של האלמנט והתדירות, על פי התדר, הסרת החלק העליון של ערימת 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 (יומן N) מגיע בגלל הזמן להכניס אלמנט לתור המקסימלי או לתור העדיפות.

מורכבות בחלל

O (N) מכיוון שאנו מאחסנים אלמנטים N יונים במקרה הגרוע ביותר. מורכבות החלל היא לינארית.

הפניות