一、版本1—有序数组中只出现一次的数字
1、题目描述
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例 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)空间复杂度中运行。
2、思路
a）使用线性时间异或运算：
b）实现规定时间复杂度的方法
3、代码
a）使用异或运算实现的代码
package cn.zifuchuan;
public class Test7 {
public static void main(String[] args) {
int[] nums = {1,1,2,3,3,4,4,8,8};
System.out.println(singleNonDuplicate(nums));
}
public static int singleNonDuplicate(int[] nums) {
int temp = 0;
for (int i = 0; i < nums.length; i++) {
temp ^= nums[i];
}
return temp;
}
}
b）二分法查找实现
package cn.zifuchuan;
public class Test7 {
public static void main(String[] args) {
int[] nums = {1, 1, 2, 2, 4, 4, 5, 5,9};
System.out.println(singleNonDuplicate(nums));
}
// public static int singleNonDuplicate(int[] nums) {
// int temp = 0;
// for (int i = 0; i < nums.length; i++) {
// temp ^= nums[i];
// }
// return temp;
// }
public static int singleNonDuplicate(int[] nums) {
int low = 0, high = nums.length - 1;
int mid = (high - low) / 2;
while(low < mid) {
if((nums[mid] == nums[mid - 1])) { //和左边相等，那么出现一次的就在右边
if((mid - low) % 2 != 0) {
low = mid + 1;
System.out.println("low=" + low + "nums[low]" + nums[low]);
} else {
high = mid - 2;
System.out.println("high=" + high + "nums[high]" + nums[high]);
}
} else if(nums[mid] == nums[mid + 1]){ //和右边相等，出现一次的就在左边
if((mid - low) % 2 != 0) {
high = mid - 1;
System.out.println("high=" + high + "nums[high]" + nums[high]);
} else {
low = mid + 2;
System.out.println("low=" + low + "nums[low]" + nums[low]);
}
}
mid = (high - low) / 2 + low; //二分中间位置
System.out.println("mid=" + mid + "mid:" + nums[mid]);
}
// System.out.println(mid);
return nums[low];
}
}
二、版本二—无须数组中找出两个只出现一次的数字
1、题目描述
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例 :
输入: [,,,,,]
输出: [,]
注意：
、结果输出的顺序并不重要，对于上面的例子， [, ] 也是正确答案。
、你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
2、代码实现
a）位运算实现
public int singleNumber(int[] nums) {
int a = 0, b = 0;
for (int i = 0; i < nums.length; i++) {
a = (a ^ nums[i]) & ~b;
b = (b ^ nums[i]) & ~a;
}
return a;
}
b）排序之后实现
public static int singleNumber(int[] nums) {
int len = nums.length;
Arrays.sort(nums);
for (int i = 0; i < len; i++) {
if(((i + 1) < (len - 1)) && (nums[i] == nums[i + 1]) ) {
i = i + 2;
continue;
} else if(((i+1) < (len - 1)) && (nums[i] != nums[i + 1])){
return nums[i];
} else {
return nums[len-1];
}
}
return 0;
}