136. Single Number 문제의 자바 해결 방법: 효율적인 알고리즘

문제

Problem_Link

문제해결방법

a linear runtime complexity =O(n)

use only constant extra space=O(1)

1. 처음 생각했던 방법은 해쉬맵을 만들어서 두번 나오지 않는것을 생각했으나, 공간복잡도를 O(1)이여야 하므로 사용할수 없음.
2. O(n) 이나 O(2n)이나 같은 O(n)이므로, 정렬을 하고 비교하는 방식으로 가능함
   1. 정렬을 한다
   2. 다음에 나오는 수가 같지 않다면 리턴

시간복잡도: O(n), 공간복잡도: O(1)

https://github.com/eunhanlee/leetcode_136_Single_Number

import java.util.*;

class Solution {
    /**
     * 배열에서 single number를 찾는 메소드입니다.
     *
     * @param nums 정수 배열
     * @return single number
     * @throws NoSuchElementException single number를 찾지 못한 경우
     */
    public int singleNumber(int[] nums) {
        // 주어진 배열을 정렬
        Arrays.sort(nums);
        
        // 연속된 두 원소씩 비교한다.
        for(int i=0; i<nums.length; i+=2){
            // 만약 두 원소가 다르면 첫 번째 원소가 single number이므로 해당 값을 리턴한다.
            if(i==nums.length-1) return nums[i];
            else if(nums[i]!=nums[i+1]){
                return nums[i];
            }
        }
        
        // 배열의 끝까지 single number를 찾지 못한 경우, NoSuchElementException을 던진다.
        // leetcode는 NoSuchElementException을 허용하지 않음.
        // 문제에서 없는 경우는 없다고 하였으므로, return 0;으로 대체해도 됨.
        throw new NoSuchElementException();
    }
}