★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（）

➤GitHub地址：

➤原文地址： 

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

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.

---

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例 1:

输入: [1,1,2,3,3,4,4,8,8]输出: 2

示例 2:

输入: [3,3,7,7,10,11,11]输出: 10

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

---

Runtime: 40 ms

Memory Usage: 19 MB

1 class Solution { 2     func singleNonDuplicate(_ nums: [Int]) -> Int { 3         var left:Int = 0 4         var right:Int = nums.count - 1 5         while (left < right) 6         { 7             var mid:Int = left + (right - left) / 2 8             if mid % 2 == 1  9             {10                 mid -= 111             }12             if nums[mid] == nums[mid + 1]13             {14                 left = mid + 215             }  16             else17             {18                 right = mid19             }20         }21         return nums[left]22     }23 }

---

40ms

1 class Solution { 2     func singleNonDuplicate(_ nums: [Int]) -> Int { 3         var low = 0 4         var high = nums.count - 1 5         var medium = (low + high)/2 6          7         while (low < high) { 8             if medium % 2 == 0 { 9                 if nums[medium] == nums[medium + 1] {10                     low = medium + 211                 } else {12                     high = medium13                 }14             } else {15                 if nums[medium] == nums[medium - 1] {16                     low = medium + 117                 } else {18                     high = medium19                 }20             }21             medium = (low + high)/222         }23         24         return nums[low]25     }26 }

---

Runtime: 40 ms

Memory Usage: 19 MB

1 class Solution { 2     func singleNonDuplicate(_ nums: [Int]) -> Int { 3  var left = 0 4         var right = nums.count 5          6         var middle = nums.count / 2 7         while middle != 0  { 8             guard middle - 1 >= 0 && middle + 1 <= nums.count-1 else 9             {10                 return nums[middle]11             }12             if nums[middle] == nums[middle-1]{13                 if middle % 2 == 0{14                     right = middle - 115                 }else{16                     left = middle + 117                 }18                 19             }else if nums[middle] == nums[middle+1] {20                 if middle % 2 == 0{21                     left = middle + 122                 }else23                 {24                     right = middle-125                 }26                 27             }else{28                 return nums[middle]29             }30             middle = (left + right)/231         }32         return nums[0]33     }34 }

---

48ms

1 class Solution { 2     func singleNonDuplicate(_ nums: [Int]) -> Int { 3         var dictionary = [Int: Int]() 4          5         for number in nums { 6             var value = dictionary[number] ?? 0 7             value += 1 8             dictionary[number] = value 9         }10         11         var result = 012         13         for key in dictionary.keys where dictionary[key] == 1 {14             result = key15             break16         }17         18         return result19     }20 }

---

68ms

1 class Solution { 2     func singleNonDuplicate(_ numbers: [Int]) -> Int { 3         func search(_ left: Int, _ right: Int) -> Int { 4             let middle = (left + right) / 2 5  6             if middle > 0 && numbers[middle - 1] == numbers[middle] { 7                 if (middle - 1) % 2 == 0 { 8                     return search(middle + 1, right) 9                 } else {10                     return search(left, middle - 2)11                 }12             }13 14             if middle < (numbers.count - 1) && numbers[middle] == numbers[middle + 1] {15                 if middle % 2 == 0 {16                     return search(middle + 2, right)17                 } else {18                     return search(left, middle - 1)19                 }20             }21 22             return numbers[middle]23         }24         return search(0, numbers.count - 1)25     }26 }