1826. 有缺陷的传感器 🔒

题目描述

实验室里正在进行一项实验。为了确保数据的准确性，同时使用两个传感器来采集数据。您将获得2个数组 sensor1 and sensor2，其中 sensor1[i] 和 sensor2[i] 分别是两个传感器对第 i 个数据点采集到的数据。

但是，这种类型的传感器有可能存在缺陷，它会导致 某一个 数据点采集的数据（掉落值）被丢弃。

数据被丢弃后，所有在其右侧的数据点采集的数据，都会被向左移动一个位置，最后一个数据点采集的数据会被一些随机值替换。可以保证此随机值不等于掉落值。

举个例子, 如果正确的数据是 [1,2,3,4,5] ，此时 3 被丢弃了, 传感器会返回 [1,2,4,5,7] (最后的位置可以是任何值, 不仅仅是 7).

可以确定的是，最多有一个 传感器有缺陷。请返回这个有缺陷的传感器的编号（1 或 2）。如果任一传感器 没有缺陷 ，或者无法确定有缺陷的传感器，则返回 -1 。

示例 1：

输入：sensor1 = [2,3,4,5], sensor2 = [2,1,3,4]
输出：1
解释：传感器 2 返回了所有正确的数据.
传感器2对第二个数据点采集的数据，被传感器1丢弃了，传感器1返回的最后一个数据被替换为 5 。

示例 2：

输入：sensor1 = [2,2,2,2,2], sensor2 = [2,2,2,2,5]
输出：-1
解释：无法判定哪个传感器是有缺陷的。
假设任一传感器丢弃的数据是最后一位，那么，另一个传感器就能给出与之对应的输出。

示例 3：

输入：sensor1 = [2,3,2,2,3,2], sensor2 = [2,3,2,3,2,7]
输出：2
解释：传感器 1 返回了所有正确的数据.
传感器 1 对第四个数据点的采集数据，被传感器2丢失了, 传感器 2 返回的最后一个数据被替换为 7 。

提示：

sensor1.length == sensor2.length
1 <= sensor1.length <= 100
1 <= sensor1[i], sensor2[i] <= 100

解法

方法一：遍历

思考

一个传感器会丢掉某个值并把后续数据前移，另一个保持正确。需要判断哪一个损坏，或无法区分。两数组只在错位后不同，暴力对齐所有丢弃位置为 \(O(n^2)\)，而 \(n\) 虽不大，结构上只需一次错位比较。

先找到第一个不同下标 \(i\)，此后把 \(sensor1[i+1:]\) 与 \(sensor2[i:]\)、以及反过来的一对比较。哪一侧无法对齐，即对应传感器丢失了数据；两边都能对齐则无法判定。

遍历两个数组，找到第一个不相等的位置 \(i\)。如果 \(i \lt n - 1\)，循环比较 \(sensor1[i + 1]\) 和 \(sensor2[i]\)，如果不相等，说明传感器 \(1\) 有缺陷，返回 \(1\)；否则比较 \(sensor1[i]\) 和 \(sensor2[i + 1]\)，如果不相等，说明传感器 \(2\) 有缺陷，返回 \(2\)。

遍历结束，说明无法确定有缺陷的传感器 🔒，返回 \(-1\)。

时间复杂度 \(O(n)\)，其中 \(n\) 为数组长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScript

class Solution:
    def badSensor(self, sensor1: List[int], sensor2: List[int]) -> int:
        i, n = 0, len(sensor1)
        while i < n - 1:
            if sensor1[i] != sensor2[i]:
                break
            i += 1
        while i < n - 1:
            if sensor1[i + 1] != sensor2[i]:
                return 1
            if sensor1[i] != sensor2[i + 1]:
                return 2
            i += 1
        return -1

class Solution {
    public int badSensor(int[] sensor1, int[] sensor2) {
        int i = 0;
        int n = sensor1.length;
        for (; i < n - 1 && sensor1[i] == sensor2[i]; ++i) {
        }
        for (; i < n - 1; ++i) {
            if (sensor1[i + 1] != sensor2[i]) {
                return 1;
            }
            if (sensor1[i] != sensor2[i + 1]) {
                return 2;
            }
        }
        return -1;
    }
}

class Solution {
public:
    int badSensor(vector<int>& sensor1, vector<int>& sensor2) {
        int i = 0;
        int n = sensor1.size();
        for (; i < n - 1 && sensor1[i] == sensor2[i]; ++i) {}
        for (; i < n - 1; ++i) {
            if (sensor1[i + 1] != sensor2[i]) return 1;
            if (sensor1[i] != sensor2[i + 1]) return 2;
        }
        return -1;
    }
};

func badSensor(sensor1 []int, sensor2 []int) int {
    i, n := 0, len(sensor1)
    for ; i < n-1 && sensor1[i] == sensor2[i]; i++ {
    }
    for ; i < n-1; i++ {
        if sensor1[i+1] != sensor2[i] {
            return 1
        }
        if sensor1[i] != sensor2[i+1] {
            return 2
        }
    }
    return -1
}

function badSensor(sensor1: number[], sensor2: number[]): number {
    let i = 0;
    const n = sensor1.length;
    while (i < n - 1) {
        if (sensor1[i] !== sensor2[i]) {
            break;
        }
        ++i;
    }
    while (i < n - 1) {
        if (sensor1[i + 1] !== sensor2[i]) {
            return 1;
        }
        if (sensor1[i] !== sensor2[i + 1]) {
            return 2;
        }
        ++i;
    }
    return -1;
}

1826. 有缺陷的传感器 🔒

题目描述

解法

方法一：遍历

评论