【剑指offer-Java版】40数组中只出现一次的数字

旧城等待， 2022-08-21 10:45 134阅读 0赞

数组中只出现一次的数字：输入一个数组，该数组中有两个数字只出现了一次，其他数字都出现了两次，求出这两个只出现了一次的数字  
要求时间复杂度为O(n)空间复杂度为O(1)

考虑一个数组中只有一个数字仅仅出现一次而其他数字都出现了两次，求这个只出现了一次的数字 – 结合异或运算的性质，两个相同数字异或的结果必为0  
那么我们只需要依次 将数组中的数据进行异或，最终结果就是那个只出现一次的数字

于是原问题就转化为如何将原数组分为两个数组，使得两个数组中各有一个值出现一次的数字，而且相同的数字都在同一个数组中  
考虑到一个数字的二进制位中，要么为0要么为1，而相等数字的指定位必相同，于是就可以根据指定位是0还是1将原数组划分为两个数组，且满足上述的要求  
另外，将两个不相同数字区分开(因为可能存在两个不相同数字的指定位是相同的)的方法是，将数组中所有的数字异或之后，结果实际上等于这两个不相等的数的异或结果  
于是可以从这个结果的二进制中取出一位非零位，以该位为标准，就可以将两个不相等的数区分开了(因为根据异或运算这个不为0的位对应于这两个数相同的位，该位置必不相同)

public class _Q40<T> {
    
        public void FindNumbersAppearOnce(int nums[]){
            if(nums == null) return;
            if(nums.length < 4) return;
    
            int resultExclusiveOr = 0;
            for(int i=0; i<nums.length; i++){
                resultExclusiveOr ^=nums[i];
            }
    
            int count = 0;
            while(true){ // 找到异或结果中，从右到左第一个不为0 的位，用于数组划分
                if((resultExclusiveOr & 0x1) == 0){ 
                    count++;
                    resultExclusiveOr = (resultExclusiveOr>>1);
                }else{
                    break;
                }
            }
    
            List<Integer> list1 = new ArrayList<>();
            List<Integer> list2 = new ArrayList<>();
            for(int i=0; i<nums.length; i++){
                if(((nums[i]>>count) & 0x1) == 0) // 负数其实也不太需要单独考虑
                    list1.add(nums[i]); 
                else 
                    list2.add(nums[i]);
            }
    
            int result1 = core(list1);
            int result2 = core(list2);
            System.out.println("first : " + result1);
            System.out.println("second : " + result2);
        }
    
        private int core(List<Integer> list){
            if(list.size() < 3) return Integer.MIN_VALUE; // 非法输入处理的有点简单粗暴
    
            int result = 0;
            for(int i=0; i<list.size(); i++){
                result ^= list.get(i);
            }
            return result;
        }
    
        }

测试代码：

public class _Q40Test extends TestCase {
        
    
        _Q40<?> appearOnce = new _Q40();
    
        public void test(){
            int nums1[] = {
       2, 4, 3, 6, 3, 2, 5, 5};
    
            appearOnce.FindNumbersAppearOnce(nums1);
        }
        }