剑指offer--数组中只出现一次的数字(java)

客官°小女子只卖身不卖艺 2024-04-17 05:40 107阅读 0赞

### 剑指offer--数组中只出现一次的数字 ###

三种常见解法：

1.  借助一个HashSet，遍历数组，如果HashSet中有该元素那么就删除这个元素，如果HashSet中没有该元素就添加该元素。最终HashSet中剩余的就是那两个没有重复的数字。  
    **时间复杂度：O(n)**  
    **空间复杂度：O(n)**
    
        public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { 
            if(array == null || array.length == 0){ 
            	return;
            }
            HashSet<Integer> set = new HashSet<Integer>();
            int[] num = new int[3];
            for(int i =0;i<array.length;i++) { 
            	if(set.contains(array[i])) { 
            		set.remove(array[i]);
            	}else { 
        			set.add(array[i]);
        		}
            }
            if(set.isEmpty()) { 
            	return;
            }else { 
        		Iterator<Integer> iterator= set.iterator();
        		int index = 0;
        		
        		while(iterator.hasNext() && index<2) { 
        			num[index] = iterator.next();
        			index++;
        		}
        	}
            num1[0] = num[0];
            num2[0]= num[1];
        }

2.利用异或运算，相同为0，不同为1。  
需要重点关注：一个数二进制从低位到高位第一个为1的寻找方法：n^(n-1)&n  
**时间复杂度：O(n)**

public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { 
        	if(array == null || array.length == 0)
        		return;
        	int allres = 0;
        	for(int i =0;i<array.length;i++) { 
        		allres^=array[i];
        	}
        	int flag = allres^(allres-1)&allres;
        	num1[0] = 0;
        	num2[0] = 0;
        	for(int i=0;i<array.length;i++) { 
        		if((array[i]&flag)>=1) { 
        			num1[0]^=array[i];
        		}
        		else { 
        			num2[0]^=array[i];
        		}
        	}
        }