题目
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
思想
折半查找，计算当前值与前后值得大小关系，得到单一元素存在的区间。时间复杂度为 O(log n)，空间复杂度为 O(1)。
示例
public int singleNonDuplicate(int[] nums, int p, int q) {
if (p == q) return nums[p];
int mid = (p + q) / 2, key = nums[mid], m = nums[mid - 1], n = nums[mid + 1];
if (m != key && n != key) return key;
boolean flag = (mid - p + 1) % 2 == 0;
if (flag) {
if (m == key) p = mid + 1;
else q = mid - 1;
} else {
if (m == key) q = mid - 2;
else p = mid + 2;
}
return singleNonDuplicate(nums, p, q);
}
网友评论