상위 K 개의 빈번한 요소

난이도 중급
자주 묻는 질문 아마존 Apple 블룸버그 게시물에서 ByteDance 자본 하나 이베이 Facebook 구글 Microsoft 신탁 포켓 보석
배열 해시 해싱 더미조회수 101

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

상위 K 개의 빈번한 요소에서 우리는 정렬 nums [], 가장 자주 발생하는 k 개의 요소를 찾습니다.

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

 

상위 K 개의 빈번한 요소

nums[] = {1}
k = 1
1

Top 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 개의 항목이 답에 기여합니다.
답변 = 3 1

암호

Top 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)), 지도를 사용했기 때문입니다. 그리고 map은 요소 삽입에 log 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 log N + N), 여기서 N은 요소의 수입니다. 최악의 경우 입력에있는 모든 숫자가 구별 될 수 있기 때문입니다.
O (log N) 요소는 요소를 최대 힙 또는 우선 순위 큐에 삽입하는 시간 때문에 발생합니다.

공간 복잡성

의 위에), 최악의 경우 N 개의 원소 이온을 저장하기 때문입니다. 공간 복잡성은 선형입니다.

참조

균열 시스템 설계 인터뷰
Translate »