[Leet Code] 136. Single Number

Single Number

 

 문제 설명

 

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

 제한 사항

 

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

 

 입출력 예

 

Example 1:

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

Example 2:

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

Example 3:

Input: nums = [1]
Output: 1

 

 Python 코드

 

Python code 

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        answer = 0
        for i in nums:
            answer = answer ^ i
        return answer

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        cnt_dict = Counter(nums) 
        items = cnt_dict.items()
        
        for key, val in items:
            if val == 1:
                answer = key
                break
                
        return answer

* 참고 링크 : https://airsbigdata.tistory.com/89

 

 C++ 코드

 

C ++ 100% 0ms code

nt singleNumber(int a[], int n) {
     //xor all numbers, the left over number would be the non repeated one
     // since the equl numbers cancel out each others bits
     int num = 0;
     for (int i = 0; i < n; ++i) {
         num ^= a[i];
     }
     return num;
    }

* 참고 링크 : https://leetcode.com/problems/single-number/discuss/43237/4-lines-of-c%2B%2B-solution

 

 출처

 

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