[LeetCode][JAVA] 540. Single Element in a Sorted Array

Contents

 

한 번만 나타나는 요소를 반환하라!

 

문제 설명

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.

Return the single element that appears only once.

지속적인 정수로 정렬된 배열의 요소는 정확히 한 번 나타는 요소를 제외하고는 항상 2배이다. 
오직 한 번 나타나는 하나의 요소를 반환하라

---

 

제한사항

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105

---

 

입출력 예시

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

Input: nums = [3,3,7,7,10,11,11]
Output: 10

---

 

설계 / 아이디어

1. 이진탐색

1. nums[중간값]이 nums[중간값 + 1 이나 - 1]과 다르면 그대로 nums[중간값]을 반환
2. 그렇지 않다면 nums[중간값]과 nums[중간값 + 1]이 같고 짝수이거나 
   nums[중간값]과 nums[중간값 - 1]이 같고 홀수라면
   start를 mid + 1로 선언하여 중간값의 오른쪽을 탐색
3. 그것도 아니라면 중간값의 왼쪽을 탐색

2. 완전탐색

1. nums[i]를 순회하며 nums[i] == nums[i+1]이 같다면 넘어간다
2. 다를 때 return nums[i]를 반환

---

 

문제 풀이

 

1. 이진 탐색

class Solution {
    public int singleNonDuplicate(int[] nums) {
        
        
		int start = 0;
        int end = nums.length - 1;
        
//      길이가 1인 경우
        if (nums.length == 1) {
            return nums[0];
        }
        
//      처음이 다른 경우
        if (nums[0] != nums[1]) {
            return nums[0];
        }
        
//      마지막이 다른 경우
        if (nums[end] != nums[end - 1]) {
            return nums[end];
        }
        
        while (start <= end) {
            int mid = (start + end) / 2;
            
            if (nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1] ) { 
                return nums[mid];
            }
            
            else if ((nums[mid] == nums[mid + 1] && mid % 2 == 0) || (nums[mid] == nums[mid - 1] && mid % 2 != 0)) {
                start = mid + 1;
            }
            
            else {
                end = mid - 1;
            }
        }
        return nums[start];
    }
}

 

2. 완전탐색

class Solution {
    public int singleNonDuplicate(int[] nums) {
        
        int once = 0;
        
        if (nums.length == 1) {
            return nums[0];
        }
        
        for (int i = 0; i < nums.length; i++) {
            
            if (i >= nums.length - 1) {
                return nums[nums.length - 1];
            }
            
            if (nums[i] == nums[i + 1]) {
                i = i + 1;
            }
            
            else {
                once = nums[i];
                return once;
            }
        }
        return once;
    }
}