SingleElementInASortedArray [source code]

public class SingleElementInASortedArray {
static
/******************************************************************************/
public class Solution {
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;
        int lo = 0, hi = n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if ((mid % 2 == 0 && mid + 1 < n && nums[mid] == nums[mid + 1]) ||
                (mid % 2 == 1 && mid - 1 >= 0 && nums[mid] == nums[mid - 1]))
                lo = mid + 1;
            else
                hi = mid;
        }
        return nums[lo];
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SingleElementInASortedArray.Solution tester = new SingleElementInASortedArray.Solution();
        int[][] inputs = {
            {1,1,2,3,3,4,4,8,8}, {2},
            {3,3,7,7,10,11,11}, {10},
            {1,1,2,3,3}, {2},
            {1,1,2,2,3,4,4,5,5}, {3},
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int[] nums = inputs[2 * i];
            int answer = inputs[1 + 2 * i][0];
            System.out.println(Printer.seperator());
            int output = tester.singleNonDuplicate(nums);
            System.out.println(Printer.wrapColor(Printer.array(nums), "magenta") + " -> " + output + Printer.wrapColor(", expected: " + answer, answer == output ? "green" : "red"));
        }
    }
}

这个问题第一反应肯定是之前一个disappeared number的问题的思路, 直接xor解决, 但是这里的要求是logN.

加上这里给出的条件是sorted, 所以也许可以尝试一下Binary Search?

整体题目本身还是比较简单的, 就是一个Binary Search的变形题目, 感觉这种binary search variation的题目出现已经不是一次两次了, 可见Binary Search的重要性.

前面总结过, Binary Search问题, 主要需要纠结的问题是:

1. termination condition: 研究最后一个最短的iteration, 考虑如果在hit或者miss的情况下, 最后lo和hi是什么一个情况;
2. header是否可以取等号.

当然, 这个问题就属于一个比较活络的variation, 单纯去从上面两个角度死考虑是没有用的, 更重要的还是理解这个题目本身, 怎样确定下一个区间.

确定下一个区间的判据, 就是mid位置的表现. 这里要判断的虽然是mid位置的值, 但是其实是通过mid位置, 来判断[0..mid]这个范围内是否存在这个single number. 如果mid左边完全正常, 那么mid所在的位置就可以准确知道的它是否和它左边还是右边的邻居相等.

这个题目说简单其实也不是非常trivial, 反正还是加深对于Binary Search的理解, 核心问题就是问自己: 怎样通过对mid的一个简单的判断就知道我们要找的hit是在左边还是右边: verbal logic;

在确定了核心搜索策略之后, 再开始纠结上面提到的两个点. 这里可以看到, 我们这里的逻辑其实只有两个branch, 这种两个branch的Binary Search其实前面好像也是碰到过的; 另外, 通过研究最后一个iteration, 事实上, 因为这个问题有点复杂, 所以干脆直接拿着一个例子来找last iteration, 而不是直接脑子里空想一个length = 2的就说一定是last iteration. 通过对这个iteration的研究, 可以看到这题其实不取等号比较好;

2018-05-17 16:24:45
这个时候的代码是这样的:

public class Solution {  
    public int singleNonDuplicate(int[] nums) {  
        int n = nums.length;  
        int lo = 0, hi = n - 1;  
        while (lo < hi) {  
            int mid = lo + (hi - lo) / 2;  
            if ((mid % 2 == 0 && mid + 1 < n && nums[mid] == nums[mid + 1]) ||  
                (mid % 2 == 1 && mid - 1 >= 0 && nums[mid] == nums[mid - 1]))  
                lo = mid + 1;  
            else  
                hi = mid - 1;  
        }  
        return nums[lo];  
    }  
}

但是这个代码是有问题的, 被人发帖指出来了:

wai.swk 0 an hour agoReport
Your code doesn't pass cases where the initial mid is the single element (for example, {1,1,2,3,3} and {1,1,2,2,3,4,4,5,5}).

然后仔细看了一下, 实际上是我二叉的写法不对: 写的是开区间写法, 但是最后二叉的更新方式和一开始的端点初始化都有点问题; 改了之后就ok了;

这个是discussion上面的一个解:

My solution using binary search. lo and hi are not regular index, but the pair index here. Basically you want to find the first even-index number not followed by the same number.

public class Solution {  
    public int singleNonDuplicate(int[] nums) {  
        // binary search  
        int n=nums.length, lo=0, hi=n/2;  
        while (lo < hi) {  
            int m = (lo + hi) / 2;  
            if (nums[2*m]!=nums[2*m+1]) hi = m;  
            else lo = m+1;  
        }  
        return nums[2*lo];  
    }  
}

这个解想法还是比较清奇的, 不过我没有理解的是, 到底是怎么知道hi = m这个做法的? 我就感觉我就是瞄准的下一个要走的区间, 所以我认为应该-1.

感觉Binary Search算法虽然看起来简单, 但是真正这些边界条件还是要考虑, 最好能像这一题一样, 相处一个适用于每一个iteration的invariant.

这个是我在discussion上面发帖的东西:

The logic behind this is very easy: for each mid, we try to find understand whether the single number is on the left half. The if header tests that nums[mid] is not single and neither is anything on its left.

• if mid is even, then there are 2m numbers on the left of mid. For the statement of nums[mid] is not single and neither is anything on its left to hold, we need the 2m numbers to the left of mid to be m pairs, and also nums[mid] be in a pair with nums[mid + 1]. Indeed, we only have to make sure in this case that nums[mid], nums[mid + 1] is a pair. You can prove by contradiction that as long as this holds, the sole single number can't be on the left of mid. Now that the statement of nums[mid] is not single and neither is anything on its left is proven, we can just go to the right half.
• if mid is odd, then to prove nums[mid] is not single and neither is anything on its left, we only need to prove that nums[mid - 1], nums[mid] is a pair. mid - 1 is even, and as long as nums[mid - 1], nums[mid - 1 + 1] forms a pair, we can actually use the argument of previous paragraph to prove that no entry to the left of mid is single. And neither is mid itself obviously. With nums[mid] is not single and neither is anything on its left proven, we can again to the right half.
• If nums[mid] is not single and neither is anything on its left not provable, then go to left half since the single number is there.

Problem Description

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1:
Input: [1,1,2,3,3,4,4,8,8]
Output: 2
Example 2:
Input: [3,3,7,7,10,11,11]
Output: 10
Note: Your solution should run in O(log n) time and O(1) space.

Difficulty:Medium
Total Accepted:11.6K
Total Submissions:21.3K
Contributor: rajaditya