在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ 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 -= 1 11 } 12 if nums[mid] == nums[mid + 1] 13 { 14 left = mid + 2 15 } 16 else 17 { 18 right = mid 19 } 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 + 2 11 } else { 12 high = medium 13 } 14 } else { 15 if nums[medium] == nums[medium - 1] { 16 low = medium + 1 17 } else { 18 high = medium 19 } 20 } 21 medium = (low + high)/2 22 } 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 - 1 15 }else{ 16 left = middle + 1 17 } 18 19 }else if nums[middle] == nums[middle+1] { 20 if middle % 2 == 0{ 21 left = middle + 1 22 }else 23 { 24 right = middle-1 25 } 26 27 }else{ 28 return nums[middle] 29 } 30 middle = (left + right)/2 31 } 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 = 0 12 13 for key in dictionary.keys where dictionary[key] == 1 { 14 result = key 15 break 16 } 17 18 return result 19 } 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 }
|
请发表评论