给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 1:
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
示例 2:
输入: [3,3,7,7,10,11,11]
输出: 10
注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
a）使用线性时间异或运算：
b）实现规定时间复杂度的方法
a）使用异或运算实现的代码
1 package cn.zifuchuan; 2 3 public class Test7 { 4 5 public static void main(String[] args) { 6 int[] nums = {1,1,2,3,3,4,4,8,8}; 7 System.out.println(singleNonDuplicate(nums)); 8 } 9 10 public static int singleNonDuplicate(int[] nums) { 11 int temp = 0; 12 for (int i = 0; i < nums.length; i++) { 13 temp ^= nums[i]; 14 } 15 return temp; 16 } 17 }
b）二分法查找实现
1 package cn.zifuchuan; 2 3 public class Test7 { 4 5 public static void main(String[] args) { 6 int[] nums = {1, 1, 2, 2, 4, 4, 5, 5,9}; 7 System.out.println(singleNonDuplicate(nums)); 8 } 9 10 // public static int singleNonDuplicate(int[] nums) { 11 // int temp = 0; 12 // for (int i = 0; i < nums.length; i++) { 13 // temp ^= nums[i]; 14 // } 15 // return temp; 16 // } 17 18 public static int singleNonDuplicate(int[] nums) { 19 int low = 0, high = nums.length - 1; 20 int mid = (high - low) / 2; 21 while(low < mid) { 22 if((nums[mid] == nums[mid - 1])) { //和左边相等，那么出现一次的就在右边 23 if((mid - low) % 2 != 0) { 24 low = mid + 1; 25 System.out.println("low=" + low + "nums[low]" + nums[low]); 26 } else { 27 high = mid - 2; 28 System.out.println("high=" + high + "nums[high]" + nums[high]); 29 } 30 } else if(nums[mid] == nums[mid + 1]){ //和右边相等，出现一次的就在左边 31 if((mid - low) % 2 != 0) { 32 high = mid - 1; 33 System.out.println("high=" + high + "nums[high]" + nums[high]); 34 } else { 35 low = mid + 2; 36 System.out.println("low=" + low + "nums[low]" + nums[low]); 37 } 38 } 39 mid = (high - low) / 2 + low; //二分中间位置 40 System.out.println("mid=" + mid + "mid:" + nums[mid]); 41 } 42 // System.out.println(mid); 43 return nums[low]; 44 } 45 }
原文：https://www.cnblogs.com/fsmly/p/10568397.html