LeetCode 面试题 10.05. 稀疏数组搜索

约 4 分钟
文章信息 7 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 程序员面试金典（第 6 版） 拼多多
标签
数组 字符串 二分查找

题目描述

✅ 面试题 10.05. 稀疏数组搜索

image-20260929105822577

题意分析

非空字符串按字典序排列，但数组中夹有空字符串占位。寻找目标单词的实际数组下标，不存在则返回 -1。空字符串不代表这一位置应按字典序排在所有单词之前，不能直接用它判断目标在哪一侧。

解法：二分 + 向右探测非空字符串

核心思路

[!blue]
保留二分框架，中点为空时向右寻找可比较的单词。 当前搜索范围为闭区间 [lo, hi]，取中点 mid，再令 probe 从 mid 向右跳过空串。探测只能在当前区间内进行，不能越过 hi 去使用已经排除的位置。

若 probe > hi，说明 [mid, hi] 全是空位，其中不存在要找的单词，直接令 hi = mid - 1。若找到非空项，则 [mid, probe - 1] 已确定全为空，可以在比较时一起排除。

若 words[probe] 小于目标，所有更左的非空项也不大于它，因此目标只能在 probe 右侧，令 lo = probe + 1。若它大于目标，probe 及其右侧的非空项都过大，而 mid 到 probe - 1 又全为空，所以可以直接令 hi = mid - 1，不必仅退到 probe - 1。相等时返回的是 probe，因为它才是单词所在的真实下标。

每轮要么返回答案，要么至少排除从中点开始的一侧范围，保证区间持续收缩。向右扫描过的空位也会随本轮被排除，不会在后续反复扫描；空位很多时可能需要线性探测，但不会因此形成无限循环。

解题步骤

  1. 建立闭区间搜索范围。
  2. 从中点向右跳过空串，探测不越过当前右界。
  3. 整段为空则收缩到左半区。
  4. 找到非空项后比较：相等返回 probe，较小则移动左界到 probe + 1，较大则移动右界到 mid - 1。
  5. lo > hi 时返回 -1。区间里全部是空串时，也会逐次缩小直到结束。

代码实现

class Solution {
    public int findString(String[] words, String s) {
        int lo = 0;
        int hi = words.length - 1;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            int probe = mid;

            // 在当前搜索范围内跳过空串，找到可作比较的探针。
            while (probe <= hi && words[probe].isEmpty()) {
                probe++;
            }

            // 中点到右界全为空串，整段可以直接排除。
            if (probe > hi) {
                hi = mid - 1;
                continue;
            }

            int cmp = words[probe].compareTo(s);

            if (cmp == 0) {
                return probe;
            } else if (cmp < 0) {
                lo = probe + 1;
            } else {
                hi = mid - 1;
            }
        }

        return -1;
    }
}

func findString(words []string, s string) int {
    lo, hi := 0, len(words)-1
    for lo <= hi {
        mid := lo + (hi-lo)/2
        probe := mid
        // 在当前搜索范围内跳过空串，找到可作比较的探针。
        for probe <= hi && words[probe] == "" {
            probe++
        }
        // 中点到右界全为空串，整段可以直接排除。
        if probe > hi {
            hi = mid - 1
            continue
        }
        if words[probe] == s {
            return probe
        } else if words[probe] < s {
            lo = probe + 1
        } else {
            hi = mid - 1
        }
    }
    return -1
}

复杂度分析

  • 时间复杂度：上界 $O(n+L\log(n+1))$，其中 $n$ 为数组长度，$L$ 为参与比较字符串的最大长度。所有空位累计最多扫描 $O(n)$ 次；每轮范围至少减半，至多进行 $O(\log(n+1))$ 次非空字符串比较，每次最坏花 $O(L)$。
  • 空间复杂度：$O(1)$。

关键点总结

[!green]

  • 有效比较点可能不同于二分中点。
  • 探测过的空段可以一并排除。
  • 没有非空探针时，也必须让搜索区间收缩。

易错点总结

[!yellow]

  • 直接拿空串作字典序判断：可能错误丢掉左侧目标。
  • 探测不限制右界：可能越界或读取已排除范围。
  • 命中返回 mid：它可能仍指向空串。
  • 探测失败直接 continue 而不更新边界：重复同一区间无法结束。

相似题目

题目 难度 关联与区别
704. 二分查找 简单 有序二分框架可复用，但本题中点为空串时没有有效比较信息，必须先寻找非空候选。
81. 搜索旋转排序数组 II 中等 同样存在无法直接判断保留半区的比较情形，需要谨慎缩边而不是强行按普通二分推进。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/80391196
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！