剑指Offer-56:数组中只出现一次的两个数字 和 数组中唯一的只出现一次的数字
程序员文章站
2022-07-15 10:38:23
...
题目:数组中只出现一次的两个数字
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
主要思路:根据异或运算的性质:数字异或它自身等于0。若数组中只有一个数字出现一次 ,其他数字都出现2次,那么从头到尾异或数组每个的数字,则最后结果就是只出现一次的数字。
相同的思路,若能把当前题目中的数组分成两个子数组,使得每个子数组都包含一个只出现一个的数字,其他数字都成对出现,则分别对两个子数组所有数字进行异或运算,就可以得到所求两个数。拆分原数组过程:异或原数组中的所有数字,得到一个非零数字a(即为两个只出现一次的数字的异或结果,其他数字都抵消了),从右向左找出a中第一个为1的位数,所求两个数在该位数上肯定不一样(位数异或为1,说明位数的值不相同,),以该位数是否为1作为划分标准,把原数组拆分成2个子数组,则所求两个数分别在这两个子数组中。
关键点:异或运算的特点,数组拆分
时间复杂度:O(n)
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
//思路:所有的数之间异或之后,结果为所求的两个数的异或
//取异或结果最右边的一个1,然后遍历数组,将其中该位置为0的进行异或,结果为所求的一个。
//然后将为1的进行异或,结果为所求的另一个。
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int num = 0;
for(int i=0; i<array.length; i++) {
num = num ^ array[i];
}
int target = num & (~num + 1);
for(int i=0; i<array.length; i++) {
if((array[i] & (~array[i] + 1)) == target) {
num1[0] = num1[0] ^ array[i];
}else {
num2[0] = num2[0] ^ array[i];
}
}
}
}
题目:数组中唯一的只出现一次的数字
在一个数组中除了一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
主要思路:基于位运算,若一个数字出现三次,那么它的二进制表示中的每一位也出现三次。把数组中的所有出现三次的数字的二进制表示的每一位分别加起来,则每一位的和都能被3整除,再把所求的那个数字的每一位分别加上去,若二进制对应位的和还能被3整除,则所求数字对应位为0,否则为1。最终,得到所求数字的二进制表示。
同理,数字出现4次5次的类似题目也可按此思路找出只出现一次的数字。
关键点:位运算
时间复杂度:O(n)
//思路:遍历数组,每个数转换成k进制之后,每一位进行求和然后与k进行取余,取余之后的数就是只出现一次的数在该位置的值。(k=3)
//后来发现根本不用转K进制,而且不用考虑最多有多少位,直接使用Int的32位就可以了
public int findNumberAppearOnce(int[] array) {
int[] nums = new int[32];
int index = 0;
for(int i=0; i<array.length; i++) {
index = 0;
while(array[i] > 0) {
if(array[i] % 2 == 0) {
nums[index] += 1;
}
index++;
array[i] = array[i]>>1;
}
}
return 0;
}