leetcode 剑指 Offer 56

leetcode 剑指 Offer 56 - II. 数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

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

示例 2：

输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：

1 <= nums.length <= 10000
1 <= nums[i] < 2^31

解法一：

使用HashMap统计每个元素出现的次数，最后再遍历一次map即可

 1 class Solution {
 2     public int singleNumber(int[] nums) {
 3         
 4         // 使用HashMap的方式，使用map统计每个元素出现的次数
 5         HashMap<Integer, Integer> map = new HashMap<>();
 6         int len = nums.length;
 7         for(int i = 0; i < len; ++i){
 8             if(map.containsKey(nums[i])){
 9                 map.put(nums[i], map.get(nums[i]) + 1);
10             }else{
11                 map.put(nums[i], 1);
12             }
13         }
14         // 遍历一遍map, 找到次数为1的数字
15         for(Map.Entry<Integer, Integer> en: map.entrySet()){
16             if(en.getValue() == 1){
17                 return en.getKey();
18             }
19         }
20         return 0;
21     }
22 }

leetcode运行时间：17ms, 空间：39.9MB

复杂度分析：

空间复杂度：Map中的键值对个数， O(n/3)

时间复杂度：一次遍历数组，一次遍历map, 所以时间复杂度为O(n)

解法二：

使用位运算，一个长度为32的int数组，记录了所有元素二进制在第i位的值之和，最后将数组第i位的值对3取余后将数组转换成二进制数，这个二进制数表示的数字即为该整数

 1 class Solution {
 2     public int singleNumber(int[] nums) {
 3         
 4         int[] arr = new int[32];
 5         int len = nums.length;
 6         for(int i = 0; i < len; i++){
 7             for(int j = 0; j < 32; j++){
 8                 arr[j] += (nums[i] & 1);      // 记录每个元素各个位的值
 9                 nums[i] >>= 1;
10             }
11         }
12 
13         int temp = 0;
14         for(int i = 31; i >= 0; i--){
15             temp <<= 1;
16             temp |= (arr[i] % 3);         // 将temp的最后一位设置成arr[i] % 3
17         }
18         return temp;
19     }
20 }

leetcode运行时间为：8ms, 空间为39.8mb

复杂度分析：

时间复杂度：时间复杂度主要是前阶段的双重 for 循环，所以时间复杂度为O(32n)

空间复杂度：一个长度为32的 int 数组, 所以空间其实可以说是O(1), 因为空间大小是固定的，不随着nums数组的元素增多而变化。