技术面试不发愁！从几个方法中探析数据结构的乐趣
发布时间：2021-06-05 09:45:54 所属栏目：大数据 来源：互联网
导读：如果你即将要面临大型科技公司的技术面试，那么数据结构和算法技巧方面的问题一定不能忘记准备。 本文就将介绍一些适合在面试使用的优化代码的小技巧。但在学习技巧之前，你得确保自己已经了解了简单的数据结构，比如树、堆、图和哈希映射。 注意，你要理解
|
如果你即将要面临大型科技公司的技术面试，那么数据结构和算法技巧方面的问题一定不能忘记准备。
本文就将介绍一些适合在面试使用的优化代码的小技巧。但在学习技巧之前，你得确保自己已经了解了简单的数据结构，比如树、堆、图和哈希映射。
注意，你要理解而不是仅仅记住它们。
技巧1：针对“第K个最小/最大元素”问题的最小/最大堆
问题:给定一个数字列表，使用堆数据结构找到第三小的元素：
[4,20,16,10,0,47，…]
当以“查找列表中第K个最小元素”的形式提出问题时，由于问题语句中的“最小”一词，自然会倾向于使用最小堆提出解决方案。这儿有一个简单的解决方案：
技术面试不发愁！从几个小技巧中探析数据结构的乐趣
构建给定列表的最小堆并调用extractMin() k次。这个解决方案的时间复杂度是O(n + kLogn)，消耗了O(n)的额外内存。
想要优化内存和时间复杂度，这儿有一个更好的解决方案：
技术面试不发愁！从几个小技巧中探析数据结构的乐趣
从数组的前k个元素构建最大堆
对于每个剩余的元素，将该元素与最大堆的根进行比较。如果它小于根，则用元素替换根并调用heapify()。
完成了第二步，堆的根将是第k个最小的元素。
时间复杂度:O(k +(n-k)Logk)
对于第K个最小的问题使用最大堆。
对于第K个最大的问题使用最小堆。
注意:对于这个问题有不同的解决方案，可以使用快速选择算法、中位数等。选择堆是因为它们更容易理解和可视化。
技巧2：使用索引映射
索引映射是在技术面试中多次使用的一种技术，它以使用更多内存为代价来节省搜索时间。
问题:用O(1)搜索时间实现最小堆数据结构。
从简单开始。只关注“搜索”部分，最小堆已经实现了。
技术面试不发愁！从几个小技巧中探析数据结构的乐趣
这是一个最小堆，它被表示为如下数组：
[0, 4, 16, 10, 20, 47]
想找到给定节点的下标，比如说10。
对数组进行线性搜索，直到找到元素10，这将花费O(n)时间。但需要O(1)时间。也许是因为想要更新这个节点的值，正在执行大量的更新，所以不想花时间去寻找元素。
很明显，除非牺牲一些资源，否则不可能神奇地拥有O(1)搜索时间。我们可以在哈希映射中保留每个节点的索引。无论何时更新堆，都需要更新这个散列映射上的索引。
对于上面的堆[0,4,16,10,20,47]，索引映射为：
{
0:0,
4:1,
16:2
10:3,
20:4
47:5
}
现在我们可以求出节点10在O(1)时间内的位置。如果更改堆中元素的顺序，还将更新它们在索引映射数据结构中的相对索引。
注意:可以使用其他的数据结构，例如索引映射的树。
追问:能对指针/引用使用同样的技术吗?
技巧3：在O(1)时间内从无序数组中删除一个元素
问题：在O(1)时间内移除[10,4,56,0,8,1]中的元素“4”。
从数组中删除一个特定的元素时，所有后续的元素都向左移动，这将花费O(n)个时间。这很完美，而且是最常用的技术，它保留了数组的顺序。
但如果你不在意元素的顺序，有一个更简单的方法可以实现O(1)时间内“删除”：用数组的最后一个元素替换要删除的元素。然后将数组大小减小1。
对于上面这个例子，删除“4”就可以写成：
[10, 1, 56, 0, 8, 1] #用最后一个元素“1”替换“4”
[10, 1, 56, 0, 8] #减少数组大小1。
追问：如果在意顺序呢?可以将其保存在不同的数据结构中吗?
技巧4：了解二分查找的基本原理
二分查找不仅仅是为了在一个有序数组中找到一个元素，它有着更强大的力量。一旦理解了它的基本原理，就会被能用它解决的问题的能力所折服。
问题：
农民约翰新建了一个有N个畜栏的仓房。给定一个大小为N的整数数组A，其中数组中的每个元素表示畜栏的位置，整数B表示奶牛的数量。他的奶牛不喜欢这个仓房的布局，这使它们在仓库中变得很有攻击性。为了防止奶牛互相伤害，约翰想把奶牛分配到畜栏里。
 （编辑：揭阳站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
