本文共 1604 字，大约阅读时间需要 5 分钟。

题目：

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.

解释：

如果直接用的异或解法，那么时间复杂度是O(n)，也可以直接用sum(set)之类的，但是不仅需要额外空间，时间复杂度也不符合要求。 看到排序，而且是要求时间复杂度为O(log n)，就应该想到用二分查找做。 先假设所有的元素都是出现两次，那么当index可以被2整除的时候，它和它后面的那个元素一定是相等的，那么说明如果一个值可以被2整除，而且和它后面的数不相等，那么这个数一定是只出现过一次的，用二分查找来找到这个数 　先判断nums[mid]是否是单个数字 　其次： 　若mid能被2整除： 　　nums[mid]和后一个数相等，属于正常情况，则单个的数在它右边 　　nums[mid]和后一个数不相等，属于不正常情况，则单个的数在它左边 　　 　若mid不能被2整除： 　　nums[mid]和后一个数相等，属于不正常情况，则单个的数在它左边 　　nums[mid]和后一个数不相等，属于正常情况，则单个的数在它右边　 python代码：

class Solution(object):    def singleNonDuplicate(self, nums):        """        :type nums: List[int]        :rtype: int        """        left=0        right=len(nums)-1        while left

c++代码：

class Solution {
   public:    int singleNonDuplicate(vector
   
    & nums) {
           int left=0,right=nums.size()-1;        while(left
    
     0 && nums_mid!=nums[mid-1] &&nums_mid!=nums_midplus)                return nums_mid;            else if(mid%2==0)            {
                   if(nums_mid==nums_midplus)                    left=mid+1;                else                    right=mid-1;            }            else            {
                   if(nums_mid==nums_midplus)                    right=mid-1;                else                    left=mid+1;             }        }        return nums[left];    }};
    
   

总结：

转载地址：http://mglcn.baihongyu.com/