哈希oj---- ＞只出现一次的数字

柔情只为你懂 2023-10-02 16:27 1阅读 0赞

**题目要求：**

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16][]

**分析：**

> **要找出只出现一次的元素，用排序时间复杂度太高，暴力解法不适用，同样处理起来不好处理，最简单的首先就是考虑用哈希表，最后，通过了解也知道，异或运算同样可以解决，并且时间复杂度也不高**

**解题思路：**

>  *  Map解决
> 
> 1.  将数组中的元素以key值的形式保存到Map中
> 2.  遍历数组时，判断value值是否为1
> 
>  *  Set解决
> 
> 1.  先将数组的第一个元素保存到Set中
> 2.  遍历数组，如果有相同的不保存，并且删除Set里面相同的元素
> 3.  将Set转换为数组并返回
> 
>  *  异或运算解决
> 
> 1.  根绝异或运算的特性，在二进制运算当中，相同为0，不同为1；

**解题代码：**

**1.Map解决**

class Solution {
        public int singleNumber(int[] nums) {
            Map<Integer,Integer> m = new HashMap<>();
    
            for(int i = 0;i < nums.length;i++){
                m.put(nums[i],m.getOrDefault(nums[i],0) + 1);
            }
    
            int[] array = new int[1];
            for(int i = 0;i < nums.length;i++){
                if(m.get(nums[i]) == 1){
                    array[0] = nums[i];
                    break;
                }
            }
    
            return array[0];
        }
    }

**2.Set解决**

class Solution {
        public int singleNumber(int[] nums) {
            Set<Integer> s = new HashSet<>();
            s.add(nums[0]);
            for(int i = 1; i < nums.length;i++){
                if(s.contains(nums[i])){
                    s.remove(nums[i]);
                }else{
                    s.add(nums[i]);
                }
            }
            Integer[] array = s.toArray(new Integer[0]);
    
            return array[0];
        }
    }

**3.异或解决**

class Solution {
        public int singleNumber(int[] nums) {
            //按位异或运算的结果有两种可能（二进制中）
            //1.相同异或为0
            //2.不同异或为1
            int ans = 0;
            for(int i = 0;i < nums.length;i++){
                ans ^= nums[i];
            }
            return ans;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAb2hhbmHvvIE_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/96ff6c83822e420ea02afe45235bf319.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAb2hhbmHvvIE=,size_20,color_FFFFFF,t_70,g_se,x_16