如何以O(logn)时间复杂度查找字符串中指定字符的全部索引？

核心思路 #

你的方向完全正确——通过预处理排序+二分查找就能达成目标：

• 预处理阶段：把字符串的每个字符和它的初始索引绑定成元组，按字符值排序（排序时间不计入要求）
• 查询阶段：用二分查找快速定位目标字符的边界，提取所有对应初始索引

具体步骤 #

1. 预处理构建有序列表

   • 将原字符串转换为(字符, 初始索引)的元组列表
   • 以字符的ASCII值为键对元组列表排序，得到字符有序的结构

2. 二分查找定位边界

   • 第一次二分查找：找到目标字符在有序列表中的第一个出现位置（左边界）
   • 第二次二分查找：找到目标字符在有序列表中的最后一个出现位置（右边界）
   • 左边界到右边界之间的所有元组，其索引值就是目标字符的全部初始索引

代码实现（Python） #

def find_all_char_indices(s, target_char):
    # 生成字符与初始索引的元组并排序
    sorted_pairs = sorted([(char, idx) for idx, char in enumerate(s)], key=lambda x: x[0])
    sorted_chars = [pair[0] for pair in sorted_pairs]
    original_indices = [pair[1] for pair in sorted_pairs]
    
    # 查找左边界：第一个等于目标字符的位置
    left, right = 0, len(sorted_chars) - 1
    first_idx = -1
    while left <= right:
        mid = (left + right) // 2
        if sorted_chars[mid] == target_char:
            first_idx = mid
            right = mid - 1  # 继续向左找更早的匹配
        elif sorted_chars[mid] < target_char:
            left = mid + 1
        else:
            right = mid - 1
    
    if first_idx == -1:
        return []  # 目标字符不存在
    
    # 查找右边界：最后一个等于目标字符的位置
    left, right = first_idx, len(sorted_chars) - 1
    last_idx = -1
    while left <= right:
        mid = (left + right) // 2
        if sorted_chars[mid] == target_char:
            last_idx = mid
            left = mid + 1  # 继续向右找更晚的匹配
        elif sorted_chars[mid] < target_char:
            left = mid + 1
        else:
            right = mid - 1
    
    # 提取所有初始索引
    return original_indices[first_idx:last_idx+1]

# 测试案例
test_str = "abacbda"
print(find_all_char_indices(test_str, 'a'))  # 输出: [0, 2, 6]
print(find_all_char_indices(test_str, 'b'))  # 输出: [1, 4]

复杂度说明 #

• 查找阶段的时间复杂度为O(logn)：两次二分查找各占O(logn)，提取索引的操作是O(k)（k为目标字符出现次数，若仅关注查找定位的时间则为O(logn)）
• 空间复杂度为O(n)：需要存储排序后的元组列表，符合空间不作限制的要求

内容的提问来源于stack exchange，提问作者AnimateBow 4809