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]
};

參考資料