Single Element in a Sorted Array
LeetCode.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.
Return the single element that appears only once.
Your solution must run in O(log n) time and O(1) space.
Example:
Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2
给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。
请你找出并返回只出现一次的那个数。
你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。
First Solution
public static int singleNonDuplicate(int[] nums) {
int res = 0;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.get(nums[i]) != null) {
map.remove(nums[i]);
} else {
map.put(nums[i], 0);
}
}
for (Integer integer : map.keySet()) {
res = integer;
}
return res;
}
Better Solution
二分法
public int singleNonDuplicate(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == nums[mid - 1]) {
//中点跟左边的相等，则判断除开中点，左边还剩几位数；
if ((mid - left) % 2 == 0) {
//若为偶数，则说明左边的存在答案值，改变right的值
right = mid - 2;
} else {
//若为奇数，则说明右边的存在答案值，改变left的值
left = mid + 1;
}
} else if (nums[mid] == nums[mid + 1]) {
//中点跟右边的相等，则判断除开中点，右边还剩几位数；
if ((right - mid) % 2 == 0) {
//若为偶数，则说明右边的存在答案值，改变left的值
left = mid + 2;
} else {
//若为奇数，则说明左边的存在答案值，改变right的值
right = mid - 1;
}
} else {//中点跟左右都不相等，直接返回
return nums[mid];
}
}
return nums[right];
}
位运算
public int singleNonDuplicate(int[] nums) {
int num = 0;
for(int i : nums){
num ^= i;
}
return num;
}