20210721面试问到的两道经典数组题(java)

这是舍友在面试京东时候让写的两道题目，经典的剑指offer上的，是用位运算解决的，而我对位运算不熟悉，借此机会，正好练习。

题目1描述

给一个数组，有1个数字只出现了一次，其它数字都出现了两次，找出这两个出现一次的数字。

题目2描述

给一个数组，有两个数字出现了1次，其他数字都出现了2次，找出这两个出现两次的数字。

基础知识复习

记住位运算符号呀

^:异或符号   相同的为0  不同的为1
&：与符号	

这些都是通过二进制来计算的，先把数字变成二进制

		1^0 = 1;
		1^1 = 0;
		0^0 = 0;
		0^1 =1;

与符号

	1&1= 1；
	0&0= 0；
	1&0 = 0；
	0&1 = 0；

题1编码

其它数字都出现了两次，那么我们可以用异或符号呀，出现偶数次的都会被变为0，出现奇数次的肯定不会了。

public class offerOnlyTwo {
    public static void main(String[] args) {
        int nums[] = new int[]{1,2,3,4,3,2,1 };
        findTwo(nums);
    }
    public static void findTwo(int nums[])
    {
        int res = 0;
        for(int i = 0;i<nums.length;i++)
        {
            res ^=nums[i];
        }
        System.out.println(res);
    }
}

题目2编码

给一个数组，有两个数字出现了1次，其他数字都出现了2次，找出这两个出现两次的数字。
大家千万别把题目搞混了，我就把题目给弄混了，搞得我都不知道是第一题还是第二题了。

public class offerNumsOnlyOnes {
    public static void main(String[] args) {
        int array[] = new int[]{1,2,3,4,1,2,3,5};
        int num1[] = new int[1];
        int num2[] = new int[1];
        FindNumsAppearOnce(array,num1,num2);
        System.out.println(num1[0]+" "+num2[0]);
    }

    public static void FindNumsAppearOnce(int [] array,int num1[] , int num2[])
    {
        if(array==null||array.length<=2)    return ;
        int ans = 0;
        for(int i =0 ;i<array.length;i++)
        {
            ans ^= array[i];
        }
        //此时的ans包含的就是两个数字的 异或
        int count = 0;
        for( ;count<array.length;count++)
        {
            if((ans &(1<<count))!=0){
                break;
            }
        }

        num1[0] = 0 ;
        num2[0] = 0 ;

        for(int i=0;i<array.length;i++)
        {
            if((array[i]&(1<<count))==0)
            {
                num1[0] = num1[0]^array[i];
            }
            else
            {
                num2[0] = num2[0]^array[i];
            }
        }


    }
}
    

总结

这两道题都是用的位运算做的，需要注意位运算的练习，也可以使用别的方法，这里没有列举了，比如，你可以先给数组排序，这样直接看相邻的元素就行了，等等，我感觉自己做的话可能就比较慢。先把这个位运算好好掌握一下，因为这个之前做题见到，但是不咋用，记住那些知识点呀。