Moment For Technology

Before the buckle 347 】 【 OJ | force output K high frequency elements

Posted on Feb. 1, 2023, 11:56 p.m. by Rania Saraf
Category: c++ Tag: c++ algorithm The heap Binary search Binary search tree

The title

  • Description: Given an array of non-empty integers, return the elements with the first k frequency.
  • The element is an integer, and the range of values is int. 1 ≤ k ≤ The number of different elements in the array, and the occurrence frequency of elements is different.
  • Requirement: The time complexity of the algorithm is O(n log n), where n is the size of the array.
  • Format of input data: integer array before semicolon and k after semicolon in input content.

The sample


1,1,1,2,2,3; 2



Interpretation of the

The whole question is divided into two parts:

Iterates through the given array of integers and counts how often elements occur. Traversal process can be sequential traversal; The frequency of occurrence of statistical elements requires us to maintain a table with integer and frequency key-value pairs. For each given input integer, it is necessary to find its corresponding key-value pairs in the maintained table, and binary search can be carried out using binary search tree. So the first part is order nlogn. In all frequencies, select the elements corresponding to the first k. A maximum heap can be maintained, with the integer, frequency key-value pair's "frequency" value as the basis for key-value pair size comparison. After adding all the elements to the heap, pop k key-value pairs from the top of the heap. The time complexity of maintaining the heap is O(nlogn), and the time complexity of popping k key-value pairs is O(klogn), so the time complexity of the second part is O(nlogn).

Programming implementation (using C++ language)

The level of the program is divided into three parts from the top to the bottom: the implementation of program logic using binary search tree and maximum heap, the implementation of general binary search tree and heap, the basic unit of processing integer, and the implementation of frequency key-value pairs.

The lower level encapsulates the technical details belonging to that level and provides the abstract interfaces required by the higher level. Specifically, when implementing the program logic, you need to insert elements into the binary search tree, but you don't care how the elements are inserted into the binary search tree. In the implementation of binary search tree, we need to know the size relation of its node elements, but we do not care how the size relation is compared.

Therefore, the program implements the following three parts:

  • Implement the program logic in the main function
  • Realize a general binary search tree class and a general heap class, provide insertion, pop-up and other basic functional interfaces.
  • Implement integer, frequency key-value pair data structure, provide size comparison overloaded operator. (For binary search trees and heaps that may need to provide different data structures, you can use class inheritance to simplify the code.)

The source code

The main function

int main() { BSTElemint, unsigned tree; // While (true) {int num; cin  num; tree.insert(Elemint, unsigned(num)); if (getchar() == '; ') break; } HeapElem_Heapint, unsigned heap(MAX); // heap (Tree.isEmpty () == false) // heap (Tree.isEmpty () == false) // heap (Tree.isEmpty () == false); unsigned k; cin  k; for (unsigned i = 0; i  k; I++) // Pop-up k top heap key pairs in the maximum heap {cout  Heap.pop ().key  endl; } return 0; // Print the integer in the key-value pair} return 0; }

The implementation of binary search tree

Template class E class Node // public: E elem; NodeE* lchild; NodeE* rchild; Node(E e) :elem(e), lchild(NULL), rchild(NULL) {} }; Private: NodeE BBB * root; private: NodeE BBB * root; Public: BST() :root(n_elem) {if (root == NULL) root = new NodeE(n_elem); else { NodeE* p = root; while (true) { if (n_elem  p-elem) { if (p-lchild == NULL) { p-lchild = new NodeE(n_elem); break; } else p = p-lchild; } else if (n_elem  p-elem) { if (p-rchild == NULL) { p-rchild = new NodeE(n_elem); break; } else p = p-rchild; } else { p-elem.CountInc(); break; }}}} E popMinimal() // Minimal {if (root-lchild == NULL) {E ret(root-elem); NodeE* to_del = root; root = root-rchild; delete to_del; return ret; } else { NodeE* p = root; NodeE* cur = p-lchild; while (cur-lchild ! = NULL) { p = cur; cur = cur-lchild; } E ret(cur-elem); p-lchild = cur-rchild; delete cur; return ret; }} bool isEmpty() {if (root == NULL) return true; else return false; }};

The realization of the heap

enum heaptype_t

template class E
class Heap // 堆
    vectorE buffer;
    heaptype_t type; // 标识堆是最大堆还是最小堆

    Heap(heaptype_t t)
        type = t;

    void insert(E elem) // 插入元素
        int i = buffer.size() - 1;
        while (_parent(i) = 0  !_in_order(_parent(i), i))
            _exchange(_parent(i), i);
            i = _parent(i);

    E pop() // 弹出堆顶元素
        E ret = top();
        if (size()  0)
            buffer[0] = buffer[size() - 1];
            int i = 0;
            while (_lchild(i)  size())
                int c;
                if (_rchild(i) = size() || _in_order(_lchild(i), _rchild(i)))
                    c = _lchild(i);
                    c = _rchild(i);
                if (!_in_order(i, c))
                    _exchange(i, c);
                    i = c;
        return ret;

    E top() // 查看堆顶元素
        return buffer[0];

    int size() // 查询堆的大小
        return buffer.size();

    int _parent(int i)
        return (i - 1) / 2;

    int _lchild(int i)
        return i * 2 + 1;

    int _rchild(int i)
        return i * 2 + 2;

    bool _in_order(int p, int c)
        if (type == MAX)
            return buffer[p] = buffer[c];
            return buffer[p] = buffer[c];

    void _exchange(int a, int b)
        E temp = buffer[a];
        buffer[a] = buffer[b];
        buffer[b] = temp;

Data structures that exist in binary search trees and maximum heaps of integer, frequency key-value pairs

Template class K, class V class Elem //  integer, frequency  key-value pair structure {public: K key; V value; Elem(K k) :key(k), value(V()) { value++; } bool Operator == (ElemK, V para);} bool Operator == (ElemK, V para); The key value pairs in the binary search tree are sorted by the key {return key == para.key; } bool operator (ElemK, V para) // Overloaded operator (ElemK, V para) // Overloaded operator (ElemK, V para); } bool operator (ElemK, V para) // Overloaded operator, the binary search tree is ordered by the key {return key  para.key; } void CountInc() // To add value to 1 {value++;} void CountInc() // To add value to 1 {value++; }}; Template class K, class V class Elem_Heap :public ElemK, V, V, V {public: Elem_Heap(ElemK, V e) :ElemK, V(e.key) { ElemK, V::value = e.value; } bool operator= (Elem_HeapK, V para) // Overload operator= (Elem_HeapK, V para) // Overload operator= (Elem K, V::value = para.value; } bool Operator = (Elem_HeapK, V para) // Overload operator, sort by value in maximum heap {return ElemK, V::value = para.value; }};

Author: Fa Hua Temple middle class small fart children @Zhihu

Home page of Zhihu: Fa Hua Temple middle class kids - Zhihu

Article: 【 OJ | buckle 347] power output before K - zhihu high frequency elements

Programming implementation (using C++ language) program level from the top to the bottom is divided into three parts: the use of binary search tree and the maximum heap implementation program logic, general binary search tree and the realization of the heap, the basic unit of processing integer, frequency key value pair implementation......
StupidPanther@ no and Fa Hua Temple middle class little boy@Zhihu is the same author, others do not reprint
About (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.