Blog Test
0%

【OJ | 力扣347】输出前 K 个高频元素

Posted on In

题目

  • 描述：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
  • 条件：元素为整数，取值范围为 int 整形。1 ≤ k ≤ 数组中不相同的元素的个数，元素出现频率不同。
  • 要求：算法的时间复杂度为 O(n log n) , n 是数组的大小。
  • 输入数据格式：输入内容中分号前为整数数组，分号后为 k。

示例

输入：

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

输出：

1
2
3
1
2

解读

整道题分为两个部分：

遍历给定的整数数组并统计元素出现频率。遍历过程采用顺序遍历即可；统计元素出现频率要求我们维护一个保存有 <整数, 频率> 键值对的表格，对于给定的每一个输入的整数，均需要在维护的表格中查找其对应的键值对，可以利用二叉搜索树进行二分查找。因此，第一部分的时间复杂度为 O(nlogn)。
在所有的频率中选择出前 k 大的所对应的元素。可以维护一个最大堆，以 <整数, 频率> 键值对的“频率”值作为键值对大小比较的依据。将所有元素加入堆后，在从堆顶弹出k个键值对即可。维护堆的时间复杂度为 O(nlogn)，弹出k个键值对的时间复杂度为 O(klogn)，因此，第二部分的时间复杂度为 O(nlogn)。

编程实现（使用 C++ 语言）

程序的层次从顶层到底层分为了 3 个部分：利用二叉搜索树和最大堆实现程序逻辑、通用二叉搜索树和堆的实现、处理的基本单位 <整数, 频率> 键值对的实现。

较低的层次封装了属于该层次的技术细节，为较高层次提供了其所需要的抽象接口。具体而言，在实现程序逻辑时，需要将元素插入二叉搜索树，但不关心元素是如何插入二叉搜索树的；在实现二叉搜索树时，需要知道其节点元素的大小关系，但不关心这个大小关系是如何比较出来的。

因此，编程实现以下三个部分：

  • 在 main 函数中实现程序逻辑
  • 实现一个通用二叉搜索树类和一个通用堆类，提供插入、弹出等基本功能接口。
  • 实现 <整数, 频率> 键值对数据结构，提供大小比较重载运算符。（对于二叉搜索树和堆可能需要提供不同的数据结构，可以利用类的继承精简代码）

源代码

main 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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); // 最大堆
	while (tree.isEmpty() == false) // 将二叉搜索树中的统计数据存入最大堆
		heap.insert(tree.popMinimal());
	unsigned k;
	cin >> k;
	for (unsigned i = 0; i < k; i++) // 在最大堆中弹出 k 个堆顶键值对
	{
		cout << heap.pop().key << endl; // 打印键值对中的整数
	}


	return 0;
}

二叉搜索树的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
template<class E>
class Node // 二叉搜索树的节点
{
public:
	E elem;
	Node<E>* lchild;
	Node<E>* rchild;

	Node(E e) :elem(e), lchild(NULL), rchild(NULL) {}
};

template<class E>
class BST // 二叉搜索树
{
private:
	Node<E>* root;

public:
	BST() :root(NULL) {}

	void insert(E 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() // 弹出最小元素
	{
		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;
	}
};

堆的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
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;
	}
};

存于二叉搜索树和最大堆的 <整数, 频率> 键值对数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
template<class K, class V>
class Elem // 存于二叉搜索树的 <整数, 频率> 键值对结构
{
public:
	K key;
	V value;


	Elem(K k) :key(k), value(V())
	{
		value++; // 当 value 的类型为 unsigned int 时，value 的初始值为 1
	}


	bool operator== (Elem<K, V> para) // 重载运算符，二叉搜索树中键值对排序的依据是 键
	{
		return key == para.key;
	}


	bool operator> (Elem<K, V> para) // 重载运算符，二叉搜索树中键值对排序的依据是 键
	{
		return key > para.key;
	}


	bool operator< (Elem<K, V> para) // 重载运算符，二叉搜索树中键值对排序的依据是 键
	{
		return key < para.key;
	}


	void CountInc() // 供二叉搜索树在插入数据时发现整数已插入时调用，使 value 加 1
	{
		value++;
	}
};

template<class K, class V>
class Elem_Heap :public Elem<K, V> // 存于最大堆的 <整数, 频率> 键值对数据结构，继承自 Elem<K, 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) // 重载运算符，最大堆中键值对排序的依据是 值
	{
		return Elem<K, V>::value >= para.value;
	}


	bool operator<= (Elem_Heap<K, V> para) // 重载运算符，最大堆中键值对排序的依据是 值
	{
		return Elem<K, V>::value <= para.value;
	}
};

作者： 法华寺中班小屁孩 @ 知乎

知乎主页： 法华寺中班小屁孩 - 知乎

文章：【OJ | 力扣347】输出前 K 个高频元素 - 知乎

编程实现（使用 C++ 语言） 程序的层次从顶层到底层分为了 3 个部分：利用二叉搜索树和最大堆实现程序逻辑、通用二叉搜索树和堆的实现、处理的基本单位 <整数, 频率> 键值对的实现……

StupidPanther 与 法华寺中班小屁孩 @ 知乎 是同一作者，他人请勿转载