刷题-只出现一次的数字-Java-位运算

145 阅读 0 评论 96 点赞

我是靠谱客的博主洁净乌龟，最近开发中收集的这篇文章主要介绍刷题-只出现一次的数字-Java-位运算，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、问题描述

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

说明：
算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
在这里插入图片描述

二、思路解答

1.思路优化
最先想到的就是暴力解决法，但是时间复杂度是n*n;
之后想到的是hash解决法，但是时间复杂度是n;

如果要时间复杂度是O（1），再根据题意，就是可以是异或运算。

2.hash表的过程
使用哈希表存储每个数字和该数字出现的次数。遍历数组即可得到每个数字出现的次数，并更新哈希表，最后遍历哈希表，得到只出现一次的数字。

三、知识点

1.异或运算
异或有交换律定理，相当于将相同的数字先异或，这样两两异或就只剩0了，然后0再和最后的一个数字异或得到最终值。
异或是机器码运算，相同为0不同为1，不管数字先后，只要两个数字相同对应的二进制都会被异或为00000000，最后剩下的就是所要找的值。

四、代码解读

1.hash表的java解决

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer i : nums) {
            Integer count = map.get(i);
            count = count == null ? 1 : ++count;
            map.put(i, count);
        }
        for (Integer i : map.keySet()) {
            Integer count = map.get(i);
            if (count == 1) {
                return i;
            }
        }
        return -1; // can't find it.
    }
}

2.异或运算Java

class Solution {
    public int singleNumber(int[] nums) {
        int ans = nums[0];
        if (nums.length > 1) {
             for (int i = 1; i < nums.length; i++) {
                 ans = ans ^ nums[i];
   }
 }
        return ans;


    
    }
}