Palo Alto 面试题:从有序数组中压缩表示缺失区间(Missing Ranges)

22次阅读
没有评论

Problem Description

You are given a sorted list of distinct integers ranging from 0 to 99.

For example:

[0, 1, 2, 50, 52, 75]

Your task is to produce a string that describes the numbers missing from the list.

In this example, the missing numbers are:

3–49, 51, 53–74, 76–99

Examples

Input:  []
Output: "0-99"
Input:  [0]
Output: "1-99"
Input:  [1, 99]
Output: "0, 2-98"
Input:  [3, 5]
Output: "0-2, 4, 6-99"

这是一道典型的 区间扫描 / 缺失区间合并题
核心在于顺序遍历数组,找出相邻元素之间的空档,并正确处理 0 和 99 的边界情况
整体时间复杂度为 O(n),非常考察对边界条件的敏感度。

正文完
 0