Find the Unique Number

给一个int的array，其中只有一个数字在array中只出现一次，其他数字都是成对出现的（一个数字出现两次），输出这个单一的数字。比如，input: [1, 1, 2, 2, 3, 5, 5, 9, 9], output: 3

Thoughts

Brute force是O(N)时间, 能比O(N)更快的只有O(lgN)的二分法. 由于是成对出现, target前和后个数一定是偶数个. 因此当nums[mid]对应的数出现两次且左边是偶数个时, target一定在右边. 同理当nums[mid]出现两次且右边是偶数个时, target一定在左边. 这道题比较有趣, 因为严格来说分界点并没有把数组分成不同性质的前后两段. 每次落点mid后, 通过len判断target在哪. 在算len时还要把mid - 1或mid + 1考虑进去. 无论怎么搞, 在考虑新范围时把当前不符合的范围全部刨除掉.

因此loop invariant 除了二分法最基本的target在nums[start, end]中外, 还有len([start, end]) % 2 == 1 ((end - start + 1) & 2 == 1).

Code

import java.util.*;

public class MyClass {
    public static int findSingle(int[] nums) {
        int start = 0, end = nums.length - 1;
        // does not quit even start == end
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (mid > 0 && nums[mid] == nums[mid - 1]) {
                int len = mid + 1;
                if ((len & 1) == 0) {
                    start = mid + 1;
                } else {
                    end = mid - 2;
                }
            } else if (mid + 1 < nums.length && nums[mid] == nums[mid + 1]) {
                int len = mid + 2;
                if ((len & 1) == 0) {
                    start = mid + 2;
                } else {
                    end = mid - 1;
                }
            } else {
                return nums[mid];
            }
        }

        return -1;
    }


    public static void main(String args[]) {
        int[] test1 = new int[]{7, 7, 9, 9, 8, 8, 6, 2, 2, 4, 4};
        int[] test2 = new int[]{7, 7, 9, 8, 8, 6, 6, 2, 2, 4, 4};
        int[] test3 = new int[]{1, 1, 2, 2, 3, 5, 5, 9, 9};
        int[] test4 = new int[]{7, 7, 9, 9, 8, 8, 6, 6, 2, 2, 4};
        int[] test5 = new int[]{7, 7, 9};
        int[] test6 = new int[]{9, 7, 7};
        int[] test7 = new int[]{9};

        System.out.println("Solution: " + findSingle(test1));
        System.out.println("Solution: " + findSingle(test2));
        System.out.println("Solution: " + findSingle(test3));
        System.out.println("Solution: " + findSingle(test4));
        System.out.println("Solution: " + findSingle(test5));
        System.out.println("Solution: " + findSingle(test6));
        System.out.println("Solution: " + findSingle(test7));
    }
}

Analysis

Errors: 1. while (start <= end) 没写==. 因次当start == end时直接跳出循环, 返回-1. 而没有进入循环体内的return.

时间复杂度O(lgN).