剑指offer004-只出现一次的数字

题目

给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。

示例 1：

输入：nums = [2,2,3,2]
输出：3

示例 2：

输入：nums = [0,1,0,1,0,1,100]
输出：100

提示：

• 1 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次

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

思路

首先这个题目一看就是有什么简便方法，比如位操作，可以消除两个重复出现的数字（1，1，2，2，3），比如这中，除了一个数字个数为1，其余个数为偶数，就可以按位操作

最正常的思路应该是计数，用Hash表存储每一个数字key出现的次数，统计次数为1的key返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }
        for (Integer key :
                map.keySet()) {
            if (map.get(key) == 1) {
                return key;
            }
        }
        return 0;
    }
}

1
2
3

解答成功:
执行耗时:5 ms,击败了27.49% 的Java用户
内存消耗:38.2 MB,击败了37.66% 的Java用户

按位计算是指每一位的和为3的倍数，取余可以计算出剩下的数字

• ← Previous Post
• Next Post →