Hackerland Radio Transmitters代码求助：18/31测试用例失败

问题情况 #

我编写的Python代码在HackerRank的Hackerland Radio Transmitters问题中仅通过13/31的测试用例，现贴出代码和思路，寻求错误分析。

我的实现思路：找到最左侧未被覆盖的房屋，在能覆盖该房屋的最右侧房屋处安装发射器，再寻找下一个未被覆盖的房屋，重复此过程。

我的代码 #

def hackerlandRadioTransmitters(x, k):
    x = set(sorted(x))
    x = list(x)
    i = 0
    # 已安装发射器数量
    count = 0
    while (i < len(x)):
        # 当前未覆盖的最左房屋位置
        loc = x[i]
        # 寻找适合安装发射器的位置
        j = i
        while (True):
            # 到达数组末尾，安装发射器并返回结果
            if (j >= len(x) - 1):
                count += 1
                return count
            # 距离未超过k则继续右移
            if (x[j] - loc < k):
                j += 1
            # 距离超过或等于k，安装发射器并更新i
            else:
                count += 1
                i = j + 1
                # 更新发射器位置
                loc = x[i - 1]
                break
        
        # 寻找下一个未被覆盖的房屋
        p = i
        while (True):
            # 到达数组末尾，直接返回结果
            if (p >= len(x) - 1):
                return count
            # 仍在发射器覆盖范围内则继续右移
            if (x[p] - loc < k):
                p += 1
            # 超出覆盖范围，更新i为下一个未覆盖房屋的索引
            else:
                i = p + 1
                break
            
    return count       

错误分析 #

代码存在以下几个关键错误：

1. 发射器安装位置的判断条件错误 #

寻找发射器安装位置时，原代码用x[j] - loc < k作为判断条件，这意味着仅当房屋位置小于loc + k时才继续右移。但实际上，我们应该选择最远的、位置不超过loc + k的房屋安装发射器（即x[j] <= loc + k），这样能最大化覆盖范围。原代码会错过x[j] == loc + k的位置，导致覆盖范围缩小，需要更多发射器。

2. 下一个未覆盖房屋的定位错误 #

• 判断条件错误：发射器的覆盖范围是[发射器位置 - k, 发射器位置 + k]，判断房屋是否被覆盖应该用x[p] <= 发射器位置 + k，而原代码用x[p] - loc < k，既没有正确对应发射器的覆盖右边界，也漏掉了等于边界的情况。
• 索引更新错误：当找到第一个未被覆盖的房屋时，应该将i设为该房屋的索引p，而原代码设为p + 1，直接跳过了这个未被覆盖的房屋，导致部分房屋未被处理。

3. 数组末尾的提前返回逻辑错误 #

在第一个循环中，当j到达数组倒数第二个元素时直接返回，这会中断后续的处理流程。正确的做法是完成当前发射器的安装后，更新i为数组长度以退出循环，而不是提前返回。

修正后的代码 #

def hackerlandRadioTransmitters(x, k):
    x = sorted(set(x))
    n = len(x)
    count = 0
    i = 0
    while i < n:
        # 找到当前未覆盖的最左房屋
        current_house = x[i]
        # 寻找能覆盖当前房屋的最右侧位置（发射器安装点）
        transmitter_idx = i
        while transmitter_idx < n and x[transmitter_idx] <= current_house + k:
            transmitter_idx += 1
        # 安装发射器
        count += 1
        # 找到该发射器能覆盖的最右侧房屋
        transmitter_pos = x[transmitter_idx - 1]
        next_uncovered_idx = transmitter_idx - 1
        while next_uncovered_idx < n and x[next_uncovered_idx] <= transmitter_pos + k:
            next_uncovered_idx += 1
        # 更新i为下一个未覆盖房屋的索引
        i = next_uncovered_idx
    return count

修正说明 #

1. 先对房屋位置去重并排序，确保处理有序的唯一位置。
2. 第一步找到能覆盖当前最左房屋的最远安装点，最大化覆盖范围。
3. 第二步找到该发射器覆盖的最右侧房屋，准确定位下一个未被覆盖的房屋索引。
4. 移除了提前返回的逻辑，确保所有房屋都被处理。

内容的提问来源于stack exchange，提问作者Kavija Karunarathna