欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

剑指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;
 }