솔루션: 불일치 설정(ver. 2)

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 드셨거나 유용하셨다면 이 게시물에 좋아요를 누르거나 추천my solution post on Leetcode's forums 해주세요.


참고: 이것은 이 문제에 대한 솔루션의 두 번째 버전입니다. 덜 복잡한 솔루션이 "쉬운"문제에 더 적합하다고 생각하지만 이 게시물은 O(N) 대신 O(1) 추가 공간의 공간 복잡성으로 솔루션을 달성하는 방법을 보여줍니다.

Leetcode 문제 #645(쉬움): 불일치 설정

설명:

(이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

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.

예:

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

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

제약 조건:

• 2 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^4

아이디어:

(이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

O(1) 추가 공간으로 이 문제를 해결하기 위해 nums를 직접 사용하여 지금까지 본 숫자를 추적할 수 있습니다. 그렇게 하려면 원래 값을 다시 쉽게 얻을 수 있는 방식으로 nums의 요소를 수정할 수 있어야 합니다.

이를 수행하는 가장 쉬운 방법 중 하나는 모드 연산자(%)를 사용하는 것입니다. 가장 큰 값 nums[i]는 10^4이므로 이 숫자를 밑수로 사용할 수 있습니다. 요소 값에 10^4를 추가하면 요소의 원래 값(num % 10^4)과 인덱스와 동일한 숫자가 표시되는지 여부(num > 10)의 두 가지를 알 수 있습니다. ^4).

그러나 nums의 값은 1-인덱싱되고 nums 자체는 0-인덱싱되므로 mod 함수를 (nums - 1) % 10^4로 이동해야 합니다.

숫자를 반복하고 이 덧셈을 적용하면 마지막에 두 번 본 값은 > 20000이고 한 번도 본 적이 없는 숫자는 < 10001임을 알 수 있습니다.

따라서 우리는 숫자를 두 번째로 반복하고 이 값을 확인하고 답(ans)에 추가한 다음 an을 반환해야 합니다.

구현:

이 솔루션에 대한 4개 언어 간의 차이점은 거의 없습니다.

자바스크립트 코드:

(이동: Problem Description || Solution Idea )

var findErrorNums = function(nums) {
    let N = nums.length, ans = [,]
    for (let i = 0; i < N; i++)
        nums[(nums[i] - 1) % 10000] += 10000
    for (let i = 0; i < N; i++)
        if (nums[i] > 20000) ans[0] = i + 1
        else if (nums[i] < 10001) ans[1] = i + 1
    return ans
};

파이썬 코드:

(이동: Problem Description || Solution Idea )

class Solution:
    def findErrorNums(self, nums):
        ans = [0,0]
        for num in nums:
            nums[(num - 1) % 10000] += 10000
        for i in range(len(nums)):
            if nums[i] > 20000: ans[0] = i + 1
            elif nums[i] < 10001: ans[1] = i + 1
        return ans

자바 코드:

(이동: Problem Description || Solution Idea )

class Solution {
    public int[] findErrorNums(int[] nums) {
        int N = nums.length;
        int[] ans = new int[2];
        for (int num : nums)
            nums[(num - 1) % 10000] += 10000;
        for (int i = 0; i < N; i++)
            if (nums[i] > 20000) ans[0] = i + 1;
            else if (nums[i] < 10001) ans[1] = i + 1;
        return ans;
    }
}

C++ 코드:

(이동: Problem Description || Solution Idea )

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int N = nums.size();
        vector<int> ans(2);
        for (int num : nums)
            nums[(num - 1) % 10000] += 10000;
        for (int i = 0; i < N; i++)
            if (nums[i] > 20000) ans[0] = i + 1;
            else if (nums[i] < 10001) ans[1] = i + 1;
        return ans;
    }
};