540. Single Element in a Sorted Array - medium
문제
You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Find this single element that appears only once.
제한사항
- Your solution should run in O(log n) time and O(1) space.
입출력 예
1
2
3
4
Example 1:
Input: [1,1,2,3,3,4,4,8,8]
Output: 2
1
2
3
4
Example 2:
Input: [3,3,7,7,10,11,11]
Output: 10
풀이
- Binary Search(Best), Divide and Conquer, Hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func divide(m map[int]int, nums[] int) {
half := len(nums) / 2
if len(nums) <= 1{
m[nums[0]]++
return
}
leftNums := nums[0 : half]
rightNums := nums[half : ]
divide(m, leftNums)
divide(m, rightNums)
}
func singleNonDuplicate(nums []int) int {
m := make(map[int]int)
divide(m, nums)
for k, v := range m {
if v == 1 {
return k
}
}
return 0
}