[LeetCode/Kotlin]Easy - 136. Single Number

Single Number - LeetCode

문제

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.

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

Constraints:

• 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.

풀이

나의 풀이법

풀이 접근 과정

처음엔 Map을 써서 개수를 세야하나 생각했으나 nums[i]의 최댓값이 너무 커서 비효율적이라는 생각이 들었다.

그래서 계속 생각을 해낸 끝에 sort를 생각해냈다.

굳이 해당 숫자가 몇개인지 계속 셀 필요 없이 sort를 하면 숫자가 바뀌기 전까지만 count를 하면 되지 않을까?

그 생각이 도달하여 아래와 같은 소스가 나왔다.

최종 소스코드

class Solution {
    fun singleNumber(nums: IntArray): Int {
        nums.sort()
        var before = nums[0]
        var cnt = 0
        nums.forEach {
            if (before != it) {
                if (cnt == 1) return before
                before = it
                cnt = 1
            } else cnt++
        }
        return nums[nums.lastIndex]
    }
}

1. nums를 오름차순으로 정렬한다.
2. 앞선 숫자를 담을 before와 해당 숫자의 갯수를 계산할 cnt를 초기화한다.
3. 현재 숫자가 before와 다르면 숫자가 바뀐 것이므로 cnt가 1인 경우 before를 리턴한다.
4. cnt가 1이 아닌 경우 single number가 아니므로 before를 바꿔준다.
5. before가 it과 같은 경우 cnt 값을 올려준다.
6. 최종적으로 마지막 인덱스 값을 리턴한다. (앞에서 리턴되지 않은 경우)

다른 풀이법

fun singleNumber(nums: IntArray): Int {
    var result = 0
    for (num in nums) {
        result = result xor num
    }
    return result
}

이 코드는 XOR(배타적 논리합) 연산자(xor)를 사용하여 정수 배열의 모든 요소를 반복하면서 중복되지 않는 숫자를 찾는다.

XOR 연산은 같은 숫자를 두 번 XOR하면 0이 되므로, 모든 숫자를 XOR 연산하면 등장 한 번만 하는 숫자만 결과에 남게 됩니다.