[剑指Offer]56-数组中数字出现的次数（位运算）

题目一数组中只出现一次的数字

题目

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字

题解

异或。
先考虑：数组中只有一个数字只出现了一次，其他数字都出现了两次，怎么找出这个数字？全部异或，结果即为所求数字。
那么，原问题可以将原数组分成两个集合，两个集合都满足上面的题目，则可求出两个出现一次的数字，那么分组方法？分组：将所有数都做异或，一定至少有一位是1，因为存在两个不相同数字。先找出这一位，然后按这一位是0/1分为两组，两组自然就满足了上面的要求，可求的结果。
综上，步骤一：分组，步骤二：全部异或求得数字。

代码

public class Main {

	public static void main(String[] args) {

		int[] arr= {2,4,3,6,3,2,5,5};

		int[] num1=new int[1];

		int[] num2=new int[1];

		FindNumsAppearOnce(arr,num1,num2);

		System.out.println(num1[0]);

		System.out.println(num2[0]);

	}

    //num1,num2分别为长度为1的数组。传出参数

    //将num1[0],num2[0]设置为返回结果

    public static void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {

    	if(array==null||array.length<2) {

    		return;

    	}

    	//所有数异或

    	int xorResult=0;

    	for(int i=0;i<array.length;++i) {

    		xorResult^=array[i];

    	}

    	//找到（最后一个）为1的位

    	int bitPos=findFirstOnePos(xorResult);

    	num1[0]=0;

    	num2[0]=0;

    	for(int i=0;i<array.length;++i) {

    		if((array[i]&bitPos)==0) {//bitPos位为0的分为一组

    			num1[0]^=array[i];//该组内所有数异或，结果即为第一个出现一次的数

    		}

    		else {//bitPos为1的分为一组

    			num2[0]^=array[i];//该组内所有数异或，结果即为第二个出现一次的数

    		}

    	}

    }

    //获得二进制最后一个1的位置

    private static int findFirstOnePos(int num) {

    	return num&(~num+1);

    }

}

题目二数组中唯一只出现一次的数字

题目

一个数组中，一个数字只出现一次，其他数字都出现三次，找出只出现一次的数字

题解

用一个32位数组，记录每个数对应位相加的和，每位%3的结果得到的数字就是所求数字。

时间复杂度O(n),空间复杂度O(1).
其他解法：排序，再找,时间复杂度O(nlogn)；或者哈希表，空间复杂度O(n).

代码

public class Main {

	public static void main(String[] args) {

		int[] arr= {1,2,3,3,2,1,4,1,2,3};

		System.out.println(occurOnce(arr));

	}

	public static int occurOnce(int[] nums) {

		int[] bitSum=new int[32];

		for(int i=0;i<nums.length;++i) {

			int bitMask=1;

			for(int j=0;j<31;++j) {

				if((nums[i]&bitMask)!=0) {

					++bitSum[j];

				}

				bitMask<<=1;

			}

		}

		int ans=0;

		for(int i=31;i>=0;--i) {//高位移的多，按从高到低位遍历

			ans<<=1;

			ans+=bitSum[i]%3;

		}

		return ans;

	}

}

巴特西

[剑指Offer]56-数组中数字出现的次数（位运算）

题目一数组中只出现一次的数字

题目

题解

相关

代码

题目二数组中唯一只出现一次的数字

题目

题解

相关

代码

最新文章

热门文章

巴特西

[剑指Offer]56-数组中数字出现的次数（位运算）

题目一 数组中只出现一次的数字

题目

题解

相关

代码

题目二 数组中唯一只出现一次的数字

题目

题解

相关

代码

最新文章

热门文章

题目一数组中只出现一次的数字

题目二数组中唯一只出现一次的数字