数组中只出现一次【两次】的数字

素颜马尾好姑娘i 2022-12-06 15:51 181阅读 0赞

## 题目描述 ##

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

## 只出现一次 ##

### 集合判断是否重复 ###

**Set.add + Set.remove**

使用Set集合存储，Set集合不存储重复值，`add()`方法返回值为boolean类型，这一特点可以利用。  
Set集合的add方法，添加成功返回true，否则返回false，而Set集合不存储重复值，所以当要添加的数与集合中已存在的数重复时，不会再进行添加操作，返回false，这时再进行remove操作，将集合中已存在的那个与要添加的数相同的元素移除，这样将作为方法参数传递过来的整型数组遍历完后，到最后集合中就只剩下了那个只出现了一次的数字。

public  int findNum(int[] arr) { 
    		Set<Integer> set = new HashSet<Integer>();
    		for(int i : arr) { 
    		    //添加不成功返回false，前加上！运算符变为true
    			if(!set.add(i)) { 
    			    //移除集合中与这个要添加的数重复的元素 
    				set.remove(i);		
    			}
    		}
    		if(set.size() == 0)	return null;
    		//如果Set集合长度为0，返回null表示没找到
    		return set.toArray(new Integer[set.size()])[0];
    	}

**HashMap** 同剑指Offer只出现一次的字符相同解法

Map<Integer, Boolean> map = new HashMap<>();
    for(int c : arr) { 
        map.put(c, !map.containsKey(c));
    }
    for(int c : arr) { 
        //获取value = true,即为只出现了一次
        if(map.get(c)) { 
            System.out.println(c);
        }
    }

### 异或 ###

使用异或运算符`^`，**相同为0，相异为1**。

要操作的数组中除了某个数字只出现了一次之外，其他数字都出现了两次，所以可以定义一个变量赋初始值为0，用这个变量与数组中每个数字做异或运算，并将这个变量值更新为那个运算结果，直到数组遍历完毕，最后得到的变量的值就是数组中只出现了一次的数字了。  
这种方法只需遍历一次数组，提高了程序运行的效率。

public int findNum(int[] arr) { 
        int num = 0;
        for (int i = 0; i < arr.length; i++) { 
            num ^= arr[i];
        }
        return num;
    }

## 出现两次 ##

### 两次遍历(直观解法) ###

public static void main(String[] args) { 
        int[] arr = { 1, 1, 2, 3, 3, 4, 5, 5};
        Arrays.sort(arr);
        int a = 0, b = 0;
        for (int i = 0; i < arr.length; i += 2) { 
            if (arr[i] != arr[i + 1]) { 
                a = arr[i];
                break;
            }
        }
        for (int j = arr.length - 1; j < arr.length; j -= 2) { 
            if (arr[j] != arr[j - 1]) { 
                b = arr[j];
                break;
            }
        }
        System.out.println(a + " " + b);
    }

### 两次异或 ###

public static void main(String[] args) { 
        int[] arr = { 1, 1, 2, 3, 3, 4, 5, 5};
        //只有两位的特殊情况处理
        int len = arr.length;
        int a = 0, b = 0;
        if (len == 2) { 
            a = arr[0];
            b = arr[1];
            System.out.println(a + " " + b);
        }
        //以flag异或累积出两个值的异或结果
        int flag = 0;
        for (int i = 0; i < len; i++) { 
            flag ^= arr[i];
        }
        //保留异或结果中的最右边一个1位
        int site = flag - (flag & (flag - 1));
        //在分组的过程中直接处理，不必再储存两个分组
        a = 0;
        b = 0;
        for (int i = 0; i < len; i++) { 
            int temp = site;
            if ((site & arr[i]) == site) { 
                a ^= arr[i];
            } else { 
                b ^= arr[i];
            }
        }
        System.out.println(a + " " + b);
    }