[AlphaGo Study] [LeetCode] [JAVA] 136. Single Number

문제 설명

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

 Follow up : Could you implement a solution with a linear runtime domplecity and without using extra memory?

제한 사항

 ☞  1 ≤ nums.length ≤ 3 * 10⁴

 ☞  -3 * 10⁴ ≤ nums[i] ≤ 3 * 10⁴

 ☞  Each element in the array appears twice except for one element which appears only once.

입출력 예

Input	Output
[2, 2, 1]	1
[4, 1, 2, 1, 2]	4
[1]	1

입출력 예 설명

#예제1

nums의 값이 2, 2, 1 일 때 2는 두 번 이고 1이 한 번 있다. 따라서 1을 출력한다.

 

leetcode.com/problems/single-number/

Single Number - LeetCode

---

문제를 풀기 전 THINK

   § 주어진 nums를 정렬.

   § 맨 처음 index부터 2개를 비교한 다음, 2개가 같으면 그 다음을 비교.

         ex) i = 0 일 때, nums[0] 과 nums[1] 을 비교하여 두 값이 서로 같으면 nums[2] 와 nums[3] 을 비교.

                이 때, i = 0에서 i = 2로 넘어가므로 i = i + 2를 해주어야 함.

   § 모두 비교했을 때 같은 값이 나왔다면, 마지막에 있는 값이 한 개 인 값이므로 해당 값을 return.

나의 Solution

import java.util.Arrays;

public class SingleNumber {
	public static int singleNumber(int[] nums) {
		int n_len = nums.length;
		
		// nums 정렬
		Arrays.sort(nums);
		
		// 2개 비교해서 같으면 2개 뒤로 넘어감.
		// ex) nums[0]이랑 nums[1] 비교한 다음 nums[2]랑 nums[3] 비교
		for(int i = 0; i < n_len - 1; i+=2) {
			if(nums[i] != nums[i + 1]) {
				return nums[i];
			} // if end
		} // for end
		
		// 다 비교했을 때 모두 같으면 마지막 값이 하나인 값
		return nums[n_len - 1];
	}
}