645. Set Mismatch

Leetcode 问题: 645. Set Mismatch
Categories:
Tags:

题目

You have a set of integers s, which originally contains all the numbers from 1 to n. Unfortunately, due to some error, one of the numbers in s got duplicated to another number in the set, which results in repetition of one number and loss of another number.

You are given an integer array nums representing the data status of this set after the error.

Find the number that occurs twice and the number that is missing and return them in the form of an array.

传入一个整数阵列 s，裡面的资料期望是从 1 到 n，但裡面有些数字发生错误，有一个数字重複了，有一个数字少了，找出这个重複的数字及缺少的数字

回传阵列 [重複的数字, 缺少的数字]

Example

Input: nums = [1,2,2,4]
Output: [2,3]

Input: nums = [1,1]
Output: [1,2]

演算法

1. 补齐阵列让索引与数字相同

原本传入的阵列是预期是从 1 到 n，所以第 1 个数字对应的索引是 0，这样索引跟整数总是会差 1

为了方便计算，让索引与数字是**相同的*，在阵列最前面补 0，让整个阵列变成 0 到 n

所以只要有索引与对应的整数资料不一样，代表有找到对应错误的地方

所以 [1,2,2,4] 插入 0 之后会变成 [0,1,2,2,4]

2. 找出差异的数字，并将数字移动到原本的位置

状况 A. 试着将错误的数字移动到原本应该要去的位置

如果按照顺序储存的话，「索引的数字」与「整数清单的数字」应该要相同，不同的话表示找到差异的地方

状况 B. 要移动的「整数清单数字」必须不等于「要移动过去的索引的数字」

因为整个整数阵列出现错误是因为有出现重複的数字，所以移动到最后，可能会导致两个重複的数字一直无穷迴圈的交换

所以为了这样的状况，当要交换的数字两个是一样的话，就停止交换

状况 C. 「整数清单的数字」小于「所有数字」

当阵列长度 n，整数最多也会只到 n，所以为了避免整数超过索引范围，加入判断条件

3. 重头到尾重新扫描一次

将整数阵列都排到索引与对应的整数资料都是相同后，重新扫描阵列

当遇到索引不等于整数资料，表示找到重複的数字了

而这个重複的数字对应的索引，就是缺少的数字

答案

交换数字的地方要小心，因为是交换索引的索引，所以如果直接用内部的 swap 方式 会导致出错，因为换到一半索引变了，就把错误的资料换到那个索引，所以必须自己写交换的部分

JavaScript

function findErrorNums(numsList) {
    // 在整数阵列前补 0，让「索引数字」与「整数资料」对应到相同数字
    numsList.unshift(0);
    for (var i = 1; i < numsList.length; i++) {
        while (numsList[i] != i && numsList[i] < numsList.length && numsList[i] != numsList[numsList[i]]) {
            // 当「整数清单的数字」与「索引的数字」不同（如果按照顺序储存的话，应该要相同，不同的话就要移动到原本的位置）
            // 「整数清单的数字」小于「所有数字」（避免移动过去超出阵列范围）
            // 「整数清单数字」不等于「要移动过去的索引」（避免数字一样，无穷迴圈不断交换）
            // 交换数字
            var tmp = numsList[i];
            numsList[i] = numsList[numsList[i]];
            numsList[tmp] = tmp;
        }
    }
    // 重複的数字
    var duplicateNumber = -1;
    // 缺少的数字
    var missingNumber = -1;
    for (var index = 1; index < numsList.length; index++) {
        var currentNumber = numsList[index];
        if (currentNumber != index) {
            // 「目前数字」与「索引数字」不同
            // 重複的数字
            duplicateNumber = currentNumber;
            // 缺少的数字
            missingNumber = index;
            break;
        }
    }
    return [duplicateNumber, missingNumber];
}

TypeScript

function findErrorNums(numsList: number[]): number[] {
    // 在整数阵列前补 0，让「索引数字」与「整数资料」对应到相同数字
    numsList.unshift(0);

    for (let i = 1; i < numsList.length; i++) {
        while (numsList[i] != i && numsList[i] < numsList.length && numsList[i] != numsList[numsList[i]]) {
            // 当「整数清单的数字」与「索引的数字」不同（如果按照顺序储存的话，应该要相同，不同的话就要移动到原本的位置）
            // 「整数清单的数字」小于「所有数字」（避免移动过去超出阵列范围）
            // 「整数清单数字」不等于「要移动过去的索引」（避免数字一样，无穷迴圈不断交换）
            // 交换数字
            let tmp = numsList[i];
            numsList[i] = numsList[numsList[i]];
            numsList[tmp] = tmp;
        }
    }

    // 重複的数字
    let duplicateNumber = -1;
    // 缺少的数字
    let missingNumber = -1;
    for (let index = 1; index < numsList.length; index++) {
        let currentNumber = numsList[index];
        if (currentNumber != index) {
            // 「目前数字」与「索引数字」不同
            // 重複的数字
            duplicateNumber = currentNumber;
            // 缺少的数字
            missingNumber = index;
            break;
        }
    }

    return [duplicateNumber, missingNumber]
};

参考资料