LeetCode中“只出现一次的数字”题解

题目

难度简单

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]输出: 1

示例 2:

输入: [4,1,2,1,2]输出: 4

题解

方法一：暴力查找

两次循环，代码略

方法二：排序

使用快速排序，复杂度O(nlogn)

方法三：hashmap哈希表

class Solution {
       public int singleNumber(int[] nums) {
           // 创建hashmap，键为对应值在数组nums中出现的次数        HashMap
   
     map = new HashMap<>();        // 遍历数组,存入hashmap        for (int i = 0; i < nums.length; i++) {
               // 获取此值在hashmap中的次数            Integer count = map.get(nums[i]);            // 将count++，如果第一次出现，将count赋值为1            count = count == null ? 1 : ++count;            // 将其值及其对应出现次数存入hashmap中            map.put(nums[i], count);        }        // 遍历hashmap哈希表        for (Integer value : map.keySet()) {
               // 如果出现次数为1，将对应值返回            Integer count = map.get(value);            if (count == 1) {
                   return value;            }        }        return -1; // can't find it.    }}

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(N)

方法四：异或运算

异或运算

运算法则：

a ^ b = b ^ a

a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c;

d = a ^ b ^ c 可以推出 a = d ^ b ^ c.

a ^ b ^ a = b.

异或运算

1、异或是一个数学运算符。应用于逻辑运算。
　2、例如：真异或假的结果是真，假异或真的结果也是真，真异或真的结果是假，假异或假的结果是假。就是说两个值相异结果为真。

n^0=n n^n=0，即任何数与0进行异或，为它本身，两个相同的数进行异或运算，会得到0。

一道有意思的题目：

很多成对出现数字保存在磁盘文件中，注意成对的数字不一定是相邻的，如2, 5,3, 4, 7,3, 4, 2,5……，由于意外有一个数字消失了，如何尽快的找到是哪个数字消失了？

思路：由于有一个数字消失了，那必定有一个数只出现一次而且其它数字都出现了偶数次。用搜索来做就没必要了，利用异或运算的两个特性，代码与此题类似，同一问题

特性

1.自己与自己异或结果为0，

2.异或满足交换律。

class Solution {
       public int singleNumber(int[] nums) {
           // 初始化res 为 nums[0]         int res = nums[0];        // 遍历数组，依次进行异或运算，由于异或运算具有交换性，所以最后的结果即为出现一次的数与0异或        for(int i = 1; i < nums.length; i++){
               res ^= nums[i];        }        // 返回此数        return res;    }}