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
Input:
1,1,1,2,2,3; 2Output:
1
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() { BST<Elem<int, unsigned>> tree; // While (true) {int num; cin >> num; tree.insert(Elem<int, unsigned>(num)); if (getchar() == '; ') break; } Heap<Elem_Heap<int, 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; Node<E>* lchild; Node<E>* rchild; Node(E e) :elem(e), lchild(NULL), rchild(NULL) {} }; Private: Node<E BBB * root; private: Node<E BBB * root; Public: BST() :root(n_elem) {if (root == NULL) root = new Node<E>(n_elem); else { Node<E>* p = root; while (true) { if (n_elem < p->elem) { if (p->lchild == NULL) { p->lchild = new Node<E>(n_elem); break; } else p = p->lchild; } else if (n_elem > p->elem) { if (p->rchild == NULL) { p->rchild = new Node<E>(n_elem); break; } else p = p->rchild; } else { p->elem.CountInc(); break; }}}} E popMinimal() // Minimal {if (root->lchild == NULL) {E ret(root->elem); Node<E>* to_del = root; root = root->rchild; delete to_del; return ret; } else { Node<E>* p = root; Node<E>* 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
{
MAX,
MIN
};
template <class E>
class Heap // 堆
{
vector<E> buffer;
heaptype_t type; // 标识堆是最大堆还是最小堆
public:
Heap(heaptype_t t)
{
type = t;
}
void insert(E elem) // 插入元素
{
buffer.push_back(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];
buffer.pop_back();
int i = 0;
while (_lchild(i) < size())
{
int c;
if (_rchild(i) >= size() || _in_order(_lchild(i), _rchild(i)))
c = _lchild(i);
else
c = _rchild(i);
if (!_in_order(i, c))
{
_exchange(i, c);
i = c;
}
else
break;
}
}
return ret;
}
E top() // 查看堆顶元素
{
return buffer[0];
}
int size() // 查询堆的大小
{
return buffer.size();
}
private:
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];
else
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 == (Elem<K, V> para);} bool Operator == (Elem<K, V> para); The key value pairs in the binary search tree are sorted by the key {return key == para.key; } bool operator> (Elem<K, V> para) // Overloaded operator> (Elem<K, V> para) // Overloaded operator> (Elem<K, V> para); } bool operator< (Elem<K, 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 Elem<K, V>, V>, V> {public: Elem_Heap(Elem<K, V> e) :Elem<K, V>(e.key) { Elem<K, V>::value = e.value; } bool operator>= (Elem_Heap<K, V> para) // Overload operator>= (Elem_Heap<K, V> para) // Overload operator>= (Elem <K, V>::value >= para.value; } bool Operator <= (Elem_Heap<K, V> para) // Overload operator, sort by value in maximum heap {return Elem<K, 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