https://leetcode.com/problems/single-element-in-a-sorted-array/#/description
https://leetcode.com/problems/single-element-in-a-sorted-array/discuss/100754/Java-Binary-Search-short-(7l)-O(log(n))-w-explanations
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.
从数组递增有序和O(log n)时间复杂度推断,题目可以采用二分查找求解。
def singleNonDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
lo, hi = 0, len(nums) - 1
while lo < hi:
mi = (lo + hi) >> 1
if nums[mi] == nums[mi - 1]:
if (mi - 1) & 1:
hi = mi - 2
else:
lo = mi + 1
elif nums[mi] == nums[mi + 1]:
if (mi + 1) & 1:
lo = mi + 2
else:
hi = mi - 1
else:
return nums[mi]
return nums[lo]https://leetcode.com/problems/single-element-in-a-sorted-array/discuss/100754/Java-Binary-Search-short-(7l)-O(log(n))-w-explanations
This method seems to be a bit simpler to understand, since it doesn't start with the left half and stays a little bit closer to the conventional solutions.
public static int singleNonDuplicate(int[] nums) {
int start = 0, end = nums.length - 1;
while (start < end) {
// We want the first element of the middle pair,
// which should be at an even index if the left part is sorted.
// Example:
// Index: 0 1 2 3 4 5 6
// Array: 1 1 3 3 4 8 8
// ^
int mid = (start + end) / 2;
if (mid % 2 == 1) mid--;
// We didn't find a pair. The single element must be on the left.
// (pipes mean start & end)
// Example: |0 1 1 3 3 6 6|
// ^ ^
// Next: |0 1 1|3 3 6 6
if (nums[mid] != nums[mid + 1]) end = mid;
// We found a pair. The single element must be on the right.
// Example: |1 1 3 3 5 6 6|
// ^ ^
// Next: 1 1 3 3|5 6 6|
else start = mid + 2;
}
// 'start' should always be at the beginning of a pair.
// When 'start > end', start must be the single element.
return nums[start];
}
https://discuss.leetcode.com/topic/82235/java-code-by-using-binary-search-o-log-n
public int singleNonDuplicate(int[] nums) {
int low = 0;
int high = nums.length-1;
int low = 0;
int high = nums.length-1;
while(low < high) {
int mid = low + (high - low)/2;
if(nums[mid] != nums[mid+1] && nums[mid] != nums[mid-1])
return nums[mid];
else if(nums[mid] == nums[mid+1] && mid % 2 == 0)
low = mid+1;
else if(nums[mid] == nums[mid-1] && mid % 2 == 1)
low = mid+1;
else
high = mid-1;
}
return nums[low];
}
https://discuss.leetcode.com/topic/82332/java-binary-search-o-log-n-shorter-than-others
My solution using binary search. lo and hi are not regular index, but the pair index here. Basically you want to find the first even-index number not followed by the same number.
public int singleNonDuplicate(int[] nums) {
// binary search
int n=nums.length, lo=0, hi=n/2;
while (lo < hi) {
int m = (lo + hi) / 2;
if (nums[2*m]!=nums[2*m+1]) hi = m;
else lo = m+1;
}
return nums[2*lo];
}
https://discuss.leetcode.com/topic/83308/using-collections-binarysearch-for-fun
Longer than writing my own binary search, but I wanted to see how this would look. I let
Collections.binarySearch
search in a special List
object which returns -1
for indexes before the single element, 0
for the index of the single element, and 1
for indexes after the single element. So I run binary search for 0
. Since my special List
object computes its entries only on the fly when requested, this solution takes O(log n) time and O(1) space. public int singleNonDuplicate(int[] nums) {
List list = new AbstractList<Integer>() {
public int size() {
return nums.length;
}
public Integer get(int index) {
if ((index ^ 1) < size() && nums[index] == nums[index ^ 1])
return -1;
if (index == 0 || index % 2 == 0 && nums[index - 1] != nums[index])
return 0;
return 1;
}
};
return nums[Collections.binarySearch(list, 0)];
}
A variation, the helper
isOff
tells whether the index is in the part that's "off" (the single element and everything after it): public int singleNonDuplicate(int[] nums) {
List list = new AbstractList<Integer>() {
public int size() {
return nums.length;
}
public Integer get(int index) {
return isOff(index) + isOff(index - 1);
}
int isOff(int i) {
return i == size() - 1 || i >= 0 && nums[i] != nums[i ^ 1] ? 1 : 0;
}
};
return nums[Collections.binarySearch(list, 1)];
}