[leetcode] 136. Single Number - C

문제

https://leetcode.com/problems/single-number/

Single Number - LeetCode

• 분류 - ?
• 난이도 - Easy
• 제약
  • 1 <= nums.length <= 3 * 10^4
  • -3 * 10^4 <= nums[i] <= 3 * 10^4
  • Each element in the array appears twice except for one element which appears only once.

 

 

 

---

답안 코드 1

접근 방법

1) 첫 번째 요소부터 탐색해서

2) 배열의 요소들과 앞에서부터 비교한 후

3) 같은 값이 발견되면 다음 요소 탐색

4) 1~3 과정 반복

코드 및 실행 결과

Runtime: 1622 ms (5.05%), Memory Usage: 6.9 MB (99.85%)

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

---

답안 코드 2

접근 방법

제약조건 -3 * 10^4 <= nums[i] <= 3 * 10^4 를 이용하여,

1) -3 * 10^4 <= index <= 3 * 10^4 인 counts 배열을 생성 및 0으로 초기화

2) nums 배열을 탐색하며 nums값에 해당하는 counts 배열의 값을 증가

3) counts값이 1인 nums값을 반환

코드 및 실행 결과

Runtime: 29 ms (44.20%), Memory Usage: 7.6 MB

int counts[60001];

int singleNumber(int* nums, int numsSize){
    int result=0;
    for(int i=0; i<60001; i++){
        counts[i] = 0;
    }
    for(int i=0; i<numsSize; i++){
        counts[nums[i]+30000]++;
    }
    for(int i=0; i<numsSize; i++){
        if(counts[nums[i]+30000] == 1) result = nums[i]; 
    }
    
    return result;
}

---

답안 코드 3 - XOR

접근 방법

nums의 요소들을 앞에서부터 XOR 연산을 하면, 최종 결과값으로 single number가 나옴

코드 및 실행 결과

Runtime: 20 ms (75.84%), Memory Usage: 7.5 MB (11.55%)

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