Open YBFACC opened 4 years ago
要去:O(log n)时间复杂度和 O(1)空间复杂度
基础思路:二分
如果mid左右都不存在与mid重复的数,则找到目标数
mid左找到与mid重复的数
mid右找到与mid重复的数
如果最后left=right,则找到目标数
var singleNonDuplicate = function (nums) { if (nums.length === 0) return null let left = 0 let right = nums.length - 1 while (left <= right) { if (left === right) return nums[left] let mid = (left + right) >> 1 if (nums[mid] === nums[mid - 1]) { if ((mid - left - 1) % 2 === 1) { right = mid - 2 } else { left = mid + 1 } } else if (nums[mid] === nums[mid + 1]) { if ((right - mid - 1) % 2 === 1) { left = mid + 2 } else { right = mid - 1 } } else { return nums[mid] } } }
540-有序数组中的单一元素
思路
要去:O(log n)时间复杂度和 O(1)空间复杂度
基础思路:二分
如果mid左右都不存在与mid重复的数,则找到目标数
mid左找到与mid重复的数
mid右找到与mid重复的数
如果最后left=right,则找到目标数
代码