剑指offer第二题 数组中只出现一次的数字
程序员文章站
2022-07-15 12:08:29
...
题目描述:
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
解题思路:
1排序O(nlogn)再比较O(n)
2.位运算(异或)方式
第一步:遍历数组找到不重复数字异或的值(相同的数字异或=0)O(n)
第二步:找到异或结果为1(也就是两个数不相同的位置,一个为0,一个为1)的最高位的位号
第三步:根据是0还是是1,把数组中的数字分为两组(相同的抵消,剩下的是非重复的数字)O(n)
代码示例:
第一种方式(排序进行比较)
public static void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
//1.排序(快速排序)O(n*n)
for(int i=0;i<array.length-1;i++){
for(int j=i+1;j<array.length;j++){
if(array[i]>array[j]){
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
}
2.
for(int i=1;i<array.length-1;i++) {
if(array[0]!=array[1]) {
num1[0]=array[0];
}
if(array[array.length-1]!=array[array.length-2]) {
num2[0]=array[array.length-1];
}
if(array[i]!=array[i+1]&&array[i]!=array[i-1]) {
if (num1[0]==0) {
num1[0]=array[i];
}
else {
num2[0]=array[i];
}
}
}
}
}
第二种方式:位异或
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
public void FindNumsAppearOnce(int[] array, int[] num1, int[] num2) {
int length = array.length;
if(length == 2){
num1[0] = array[0];
num2[0] = array[1];
return;
}
//第一步:找到异或结果
int bitResult = 0;
for(int i = 0; i < length; ++i){
bitResult ^= array[i];
}
//第二步:找到某位不相等的位数,根据最高位
//第三步:根据这位是0还是1,把数组中元素分为两组,每组异或剩下非重复的值
int index = findFirst1(bitResult);
for(int i = 0; i < length; ++i){
if(isBit1(array[i], index)){
num1[0] ^= array[i];
}else{
num2[0] ^= array[i];
}
}
}
private int findFirst1(int bitResult){
int index = 0;
while(((bitResult & 1) == 0) && index < 32){
bitResult >>= 1;
index++;
}
return index;
}
private boolean isBit1(int target, int index){
return ((target >> index) & 1) == 1;
}
}
上一篇: 剑指offer——第40题——数组中只出现一次的数字
下一篇: 输入10个数,输出最大值和平均值。
推荐阅读