难度: Easy
Submission
运行时间: 24 ms
内存: 16.1 MB
class Solution:
def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:
N = len(sensor1)
i = 0
while i < N and sensor1[i] == sensor2[i]:
i += 1
if i >= N-1: return -1
res = []
if sensor1[i:N-1] == sensor2[i+1:]:
res.append(1)
if sensor1[i+1:] == sensor2[i:N-1]:
res.append(2)
if len(res) in (0, 2): return -1
return res[0]
Explain
此题目的目的是判断两个传感器数组中哪一个可能存在缺陷。两个传感器在某一点之前读数相同，但之后会有一个错误。题解的思路是首先找到第一个不同的索引位置 i。如果所有位置的读数都相同，或者只有最后一个位置不同，那么无法判断哪一个传感器有缺陷，返回 -1。如果找到不同点后，检查 sensor1 从不同点后一位到末尾是否与 sensor2 从不同点到倒数第二位相同；检查 sensor2 从不同点后一位到末尾是否与 sensor1 从不同点到倒数第二位相同。根据这两个比较结果确定哪个传感器可能有缺陷。
时间复杂度: O(N)
空间复杂度: O(1)
class Solution:
def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:
N = len(sensor1) # 获取数组长度
i = 0 # 初始化索引
# 寻找第一个不相等的位置
while i < N and sensor1[i] == sensor2[i]:
i += 1
# 如果所有读数相同或只有最后一个读数不同，无法判断
if i >= N-1: return -1
res = [] # 存储可能有缺陷的传感器编号
# 比较两个传感器的读数，确定故障的传感器
if sensor1[i:N-1] == sensor2[i+1:]:
res.append(1)
if sensor1[i+1:] == sensor2[i:N-1]:
res.append(2)
# 如果没有或两个都有可能出错，返回-1
if len(res) in (0, 2): return -1
return res[0] # 返回有缺陷的传感器编号
Explore
这种比较方式基于假设其中一个传感器在位置`i`发生了一次性的错误，导致它的数据从这个位置错位了。比较`sensor1[i:N-1]`与`sensor2[i+1:]`是为了测试如果`sensor2`在位置`i`错失了一个数据点（即数据从`i+1`开始是正确的），剩余部分是否与`sensor1`匹配。这样可以检测是否是`sensor2`在位置`i`发生了数据错位。
根据题解逻辑，如果在数组中间位置发现第一个不同的读数，然后之后的读数又全部相同，算法会通过比较错位之后的数据判断哪个传感器可能有问题。例如，如果`sensor1[i:N-1]`与`sensor2[i+1:]`相同而`sensor1[i+1:]`与`sensor2[i:N-1]`不同，则说明`sensor2`可能在`i`位置有缺陷。如果两种比较都不相同或者都相同，则算法返回-1，表示无法确定哪个传感器有缺陷。
是的，这种情况下返回-1意味着无法确定哪个传感器有缺陷。因为只有最后一个位置不同，无法通过错位比较的方式来判断是哪一个传感器的读数发生了错误，因为没有足够的后续数据来验证哪一个传感器的数据在错位后与另一个传感器的数据一致。
在这两种情况下，算法都会返回-1。如果两个传感器的数据完全相同，那么无法通过数据来判断哪个传感器可能有缺陷，因为没有任何差异点可以用来分析。同样，如果切片比较的结果都相同，这也意味着无法确定是哪个传感器的读数发生了错位，因为两种可能的错位情况都能使剩余的数据匹配对方的数据。在这种情况下，返回-1是表示无法从给定数据中确定缺陷传感器的唯一合理结论。