136. Single Number

주어진 정수 배열에서 한 번만 나타나는 유일한 숫자를 찾는 문제입니다. 이 문제는 비트 연산을 사용하여 풀 수 있는데, 아래는 문제의 자세한 설명입니다:

문제 설명:

정수 배열 nums가 주어집니다. 이 배열에는 오직 한 번만 나타나는 숫자가 하나만 있고, 나머지 숫자들은 모두 두 번씩 나타납니다. 오직 한 번만 나타나는 숫자를 찾아서 반환하세요.

예시:

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

위의 예시에서, 배열 nums에는 4가 하나만 나타나고, 나머지 숫자는 2번씩 나타나므로 4를 반환해야 합니다.

노트:

시간복잡도 O(n)과 추가 메모리 사용 없이 문제를 해결해야 합니다.
이 문제를 해결하는 한 가지 방법은 비트 연산을 사용하는 것입니다. 비트 연산을 사용하면 추가 메모리를 사용하지 않고도 문제를 효과적으로 해결할 수 있습니다. 주어진 배열을 모두 XOR 연산하면 유일한 숫자를 찾을 수 있습니다. XOR 연산은 다음과 같은 특징을 갖습니다:

어떤 숫자와 0을 XOR하면 그 숫자 자체가 반환됩니다: x ^ 0 = x
어떤 숫자와 그 자체를 XOR하면 0이 반환됩니다: x ^ x = 0
XOR 연산은 순서에 상관없이 합쳐질 수 있습니다: a ^ b ^ c = (a ^ b) ^ c
따라서, 주어진 배열을 모두 XOR 연산하면, 나타나는 숫자는 0과 XOR되어 없어지고, 유일한 숫자만 남게 됩니다. 이것이 문제를 해결하는 핵심 아이디어입니다.

 

   int singleNumber(vector<int>& nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }

 

C# 코드:

 public int SingleNumber(int[] nums) {
        int ret=0;
        Array.Sort(nums);
        int init = 30001;
        bool isChecked = false;
        for(int i=0;i<nums.Length;i++){
            ret = nums[i];
            if(nums[i]!=init && isChecked==false){
                init = nums[i];
                isChecked = true;
            }
            else if(nums[i] != init && isChecked){
                ret = init;
                break;
            }
            else if(nums[i] == init && isChecked){
                isChecked = false;
            }
        }
        
    return ret;
    }

 

 이 코드는 배열 nums에서 단 한 번 나타나는 유일한 숫자를 찾는 방법으로 접근합니다.

ret 변수: 이 변수는 결과를 저장하는 데 사용됩니다. 초기값은 0으로 설정됩니다.

Array.Sort(nums): 배열 nums를 정렬합니다. 이것은 정렬된 배열을 사용하려는 의도로 보입니다.

init 변수: 이 변수는 현재까지 확인한 숫자를 저장하는 데 사용됩니다. 초기값은 30001로 설정됩니다.

isChecked 변수: 이 변수는 현재까지 확인한 숫자가 있는지 여부를 나타내는 플래그입니다. 초기값은 false로 설정됩니다.

반복문: for 루프를 사용하여 배열 nums를 순회합니다.

nums[i]!=init && isChecked==false: 현재 확인한 숫자가 이전까지 확인한 숫자와 다르고, 아직 확인한 숫자가 없는 경우(isChecked가 false), init 변수를 현재 숫자로 설정하고 isChecked를 true로 변경합니다.

nums[i] != init && isChecked: 현재 확인한 숫자가 이전까지 확인한 숫자와 다르고, 이미 확인한 숫자가 있는 경우, ret 변수에 init 값을 저장하고 반복문을 종료합니다.

nums[i] == init && isChecked: 현재 확인한 숫자가 이전까지 확인한 숫자와 같고, 이미 확인한 숫자가 있는 경우, isChecked를 false로 변경하여 다음 반복에서 새로운 숫자를 확인할 수 있도록 합니다.

반복문이 끝나면 ret에 유일한 숫자가 저장되어 반환됩니다.