[c/LeetCode] Single Number

1. 첫 번째 아이디어
그냥 배열 돌면서 같은 값이 있는 경우는 flag를 0으로 해서 탈출하고, 같은 값이 없으면 1이 되므로 return 하도록 작성함
아쉽지만 o(n^2)이다.
856ms/ 7.3MB

int singleNumber(int* nums, int numsSize){
    int a;
    int flag;
    
    for(int i = 0; i < numsSize; i++)
    {
        a = nums[i];
        flag = 1;
        for(int j = 0; j < numsSize; j++)
        {
            if (a == nums[j] && i != j)
            {
                flag = 0;
                break;
            }
        }
        if (flag)
        {
            return a;
        }
    }
    return 1;
}

2. 두 번째 아이디어 (빌려옴)
XOR 연산자인 ^를 사용하는 것이다.
XOR은 xy' + x'y, 즉 서로 다른 경우에는 1을 return 한다.
a ^ a -> 0
0 ^ b -> b
이런 식이기 때문에 모든 배열의 값을 XOR 한다면 같은 것들은 0이 되고 다른 것은 b가 되기 때문에 정답이 된다.

int singleNumber(int* nums, int numsSize){
    int sum;
    
    for(int i=0;i<numsSize;i++)
    {
        sum ^= nums[i];
    }
    return sum;
    
}