DEV Community
·
一个算法统治所有
💡
原文英文，约1000词，阅读约需4分钟。
📝
内容提要
在一次面试中，我面临一个算法挑战：找出缺失的连续数字。我通过归纳法和二分查找设计了一个“最左边1”的算法，时间复杂度为O(log n)，适用于多种场景以寻找特定元素的边界。
🎯
关键要点
- 面试中遇到算法挑战：找出缺失的连续数字。
- 初步思路是通过求和找出缺失的数字，时间复杂度为O(n)。
- 提出了O(log n)的解决方案，利用二分查找算法。
- 算法的关键在于观察数组元素的索引与数字之间的关系。
- 通过归一化函数简化问题，寻找0和1的边界。
- 算法步骤包括设置左右指针，逐步缩小查找范围。
- 最终确定缺失数字的索引与值的关系，时间复杂度为O(log n)。
- 该算法可应用于多种场景，寻找特定元素的边界。
❓
延伸问答
如何在面试中找到缺失的连续数字？
可以通过归纳法和二分查找设计一个算法，时间复杂度为O(log n)。
什么是‘最左边1’算法？
‘最左边1’算法用于在排序的0和1列表中找到第一个1的位置，时间复杂度为O(log n)。
该算法的时间复杂度是多少？
该算法的时间复杂度为O(log n)。
如何通过归一化函数简化问题？
通过归一化函数，可以将问题转化为在0和1的列表中寻找第一个1的位置。
该算法可以应用于哪些场景？
该算法适用于寻找具有特定边界的元素，例如小于某个数字的元素在左侧，或所有偶数在左侧等。
如何设置左右指针进行查找？
设置左指针为0，右指针为列表长度减1，然后根据条件逐步缩小查找范围。
➡️
