Comment on page

540.Single-Element-in-a-Sorted-Array

540. Single Element in a Sorted Array

题目地址

题目描述

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.
​
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

代码

Approach 0: use XOR

O(n)
class Solution {
public int singleNonDuplicate(int[] nums) {
int res = 0;
for (int num : nums) {
res ^= num;
}
return res;
}
}
O(logN)
class Solution {
public int singleNonDuplicate(int[] nums) {
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
// 0: 前一个数组为奇数,1:前一个数组为偶数
boolean halvesAreEven = (hi - mid) % 2 == 0;
if (nums[mid] == nums[mid + 1]) {
if (halvesAreEven) {
// Case 1: Mid’s partner is to the right, and the halves were originally even
lo = mid + 2;
} else {
// Case 2: Mid’s partner is to the right, and the halves were originally odd
hi = mid - 1;
}
} else if (nums[mid - 1] == nums[mid]) {
if (halvesAreEven) {
// Case 3: Mid’s partner is to the left, and the halves were originally even
hi = mid - 2;
} else {
// Case 4: Mid’s partner is to the left, and the halves were originally odd
lo = mid + 1;
}
} else {
return nums[mid];
}
}
​
return nums[lo];
}
}
Approach #3 Binary Search on Evens indexes Only
O(logN)
class Soluton {
public int singleNonDuplicate(int[] nums) {
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (mid % 2 == 1) mid--;
if (nums[mid] == nums[mid + 1]) {
lo = mid + 2;
} else {
hi = mid;
}
}
return nums[lo];
}
}