Leetcode 刷题 -temp_136. 只出现一次的数字

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

说明：

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

示例 1:

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

示例 2:

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

分析：

本题的要求中，说明出现一次的数字只有一个，否则，该题就无法用 按位异或 的方式做。同时，该题限制不适用额外的空间，如果不限制，则直接使用map字典进行数字出现次数的统计。

解答：

• 第一种方式：按位异或解决
• 第二种方式：采用map字典，占用额外空间方式解决

项目源码：

package temp;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author Janson
 * @Date 2022/2/13 15:20
 * @Version 1.0
 */
public class SingleNumber {
    public static void main(String[] args) {
//        int[] nums = new int[]{2,2,1};
        int[] nums2 = new int[]{4,1,2,1,2};

        int single = 0;
        for (int i=0;i< nums2.length;i++){
            single = single ^ nums2[i];
        }
        System.out.println("按位异或方式实现：" + single);
        List mapSingle = mapSingle(nums2);
        System.out.println("map字典实现："+mapSingle);
    }
    //如果出现两个次数为 1 的数字，直接用map字典，按位异或暂时没法用
    private static List mapSingle(int[] nums){
        ArrayList<Object> singleNum = new ArrayList<>();
        Map<Integer, Integer> single = new HashMap<>();
        for (int i=0;i<nums.length;i++){
            single.put(nums[i],single.getOrDefault(nums[i],0)+1);
        }
        for (int reuslt: single.keySet()) {
            if (single.get(reuslt)==1)
                singleNum.add(reuslt);
        }
        return singleNum;
    }
}

执行结果

但是如果改变题目中的条件，如果所给数字中有两个一次的数字，按位异或方式就出错了：

package temp;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @Author Janson
 * @Date 2022/2/13 15:20
 * @Version 1.0
 */
public class SingleNumber {
    public static void main(String[] args) {
//        int[] nums = new int[]{2,2,1};
        int[] nums2 = new int[]{4,1,2,1,2,3};

        int single = 0;
        for (int i=0;i< nums2.length;i++){
            single = single ^ nums2[i];
        }
        System.out.println("按位异或方式实现：" + single);
        List mapSingle = mapSingle(nums2);
        System.out.println("map字典实现："+mapSingle);
    }
    //如果出现两个次数为 1 的数字，直接用map字典，按位异或暂时没法用
    private static List mapSingle(int[] nums){
        ArrayList<Object> singleNum = new ArrayList<>();
        Map<Integer, Integer> single = new HashMap<>();
        for (int i=0;i<nums.length;i++){
            single.put(nums[i],single.getOrDefault(nums[i],0)+1);
        }
        for (int reuslt: single.keySet()) {
            if (single.get(reuslt)==1)
                singleNum.add(reuslt);
        }
        return singleNum;
    }
}

执行结果（从结果看出，按位异或出错了，但是map字典正确输出了出现一次的数）