[leetcode #540] Single Element in a Sorted Array

Problem

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.

Your solution must run in O(log n) time and O(1) space.

Example 1:

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

Example 2:

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

Constraints:

・ 1 <= nums.length <= 10⁵
・ 0 <= nums[i] <= 10⁵

Idea

이 문제를 가장 풀기 쉬운 방법은 모든 원소를 xor 연산하는 것이다. 그러면 바로 답이 나온다.

하지만 난이도가 medium인 것으로 볼 때 xor 연산으로 풀면 안 된다. 게다가 주어진 nums array도 정렬된 array기 때문에 정렬이 연관없는 xor 연산으로 풀어선 더더욱 안 된다. 그리고 time complexity는 O(logn)이고,space complexity는 O(1)로 하라고 명시가 되어 있다.

그래서 결국 binary search로 풀었다. Solution의 member 변수로 nums array를 사용했지만, nums와 똑같은 값을 단지 복사하며 편의를 위해 사용된 것이기 때문에 추가적인 메모리는 사용하지 않았다고 보는 것이 맞다. (함수에 인자로 넣어주는 것이 귀찮아 클래스의 멤버 변수를 사용했다.)

binary search의 기본이라 할 수 있는 재귀함수를 사용해서 풀었다. 주어진 array를 잘 보면 nums array는 항상 홀수의 원소를 가지고 있다는 것을 알 수 있다. 또한 가운데 index를 기준으로 array를 두 개로 나눴을 때 원소의 개수가 짝수인 경우와 홀수인 경우에 single element의 위치가 각기 다르다는 사실도 발견할 수 있다.

재귀함수에서 값을 찾을 때는 가운데 index의 값이 좌우와 다를 경우 single element를 찾은 것이다. 문제는, 가운데 index의 값이 single element가 아닐 때다.

Example 1을 보면 single element를 가지고 있는 [1,1,2,3] array의 원소 개수는 짝수이다. 즉 binary search를 했을 때 subarray의 개수가 짝수인 경우, 가운데 값과 일치하는 값을 가지고 있는 쪽의 subarray를 탐색하면 된다.

Example 2를 보면 single element를 가지고 있는 [10,11,11] array의 원소 개수는 홀수다. 이 때는 가운데 값과 일치하는 값을 가지고 있는 쪽이 아니라 일치하지 않는 값을 가지고 있는 subarray를 탐색해야 한다.

위 과정을 계속 반복하면 원소가 하나인 element가 나올 때까지 또는 양옆의 값과 다른 값을 가진 원소가 나올 때까지 array를 탐색한다.

Solution

class Solution {
    int[] nums;

    public int singleNonDuplicate(int[] nums) {
        this.nums = nums;

        return findSingleElement(0, nums.length-1);
    }

    private int findSingleElement(int startIndex, int endIndex) {
        if (startIndex == endIndex)
            return nums[startIndex];

        int mid = startIndex + (endIndex - startIndex) / 2;
        boolean isEven = (mid - startIndex) % 2 == 0;

        if (nums[mid] != nums[mid-1] && nums[mid] != nums[mid+1])
            return nums[mid];

        if (isEven) {
            if (nums[mid] == nums[mid-1])
                return findSingleElement(startIndex, mid-2);
            else
                return findSingleElement(mid+2, endIndex);
        } else {
            if (nums[mid] == nums[mid-1])
                return findSingleElement(mid+1, endIndex);
            else
                return findSingleElement(startIndex, mid-1);
        }
    }
}

Reference

https://leetcode.com/problems/single-element-in-a-sorted-array/