Leetcode 136. 只出现一次的数字-蒲公英云

Leetcode 136. 只出现一次的数字

向右看齐 2022-09-01 00:04 339阅读 0赞

题目重述

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

说明：

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

示例 1:

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

示例 2:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一(哈希)

使用哈希存储各数字出现的次数，最后取出即可

代码实现

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);
        }
        for (Map.Entry<Integer,Integer> e : m.entrySet())
        {
            if(e.getValue() == 1)
            {
                return e.getKey();
            }
        }
        return 0;
    }
}

思路二(位运算-异或)

数组中的全部元素的异或运算结果即为数组中只出现一次的数字。

Leetcode官方题解：
在这里插入图片描述

代码实现

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