北海哪里做网站,怎样做专业网站,禹城网站制作,北京市工商注册登记网【问题描述】[第136#xff0c;137题][只出现一次的数字]
给定一个非空整数数组#xff0c;除了某个元素只出现一次以外#xff0c;其余每个元素均出现了N次。找出那个只出现了一次的元素。[第136题]N 2
输入: [2,2,1]
输出: 1
[第137题]N3
输入: [2,2,3,2]
输出: 3【解答…【问题描述】[第136137题][只出现一次的数字]
给定一个非空整数数组除了某个元素只出现一次以外其余每个元素均出现了N次。找出那个只出现了一次的元素。[第136题]N 2
输入: [2,2,1]
输出: 1
[第137题]N3
输入: [2,2,3,2]
输出: 3【解答思路】
[第136题]
1.HashSet
时间复杂度O(N) 空间复杂度O(N)
public int singleNumber(int[] nums) {HashSetInteger set new HashSet();for (int i 0; i nums.length; i) {if (!set.contains(nums[i])) {set.add(nums[i]);} else {set.remove(nums[i]);}}return set.iterator().next();
}
2. 异或 0 ⊕ 0 0 1 ⊕ 1 0 0 ⊕ 1 1 1 ⊕ 0 1 a ⊕ b ⊕ a ⊕ b ⊕ c ⊕ c ⊕ d( a ⊕ a ) ⊕ ( b ⊕ b ) ⊕ ( c ⊕ c ) ⊕ d0 ⊕ 0 ⊕ 0 ⊕ dd时间复杂度O(N) 空间复杂度O(1)
public int singleNumber(int[] nums) {int ans 0;for (int i 0; i nums.length; i) {ans ^ nums[i];}return ans;
}
[第137题]
1. HashMap
时间复杂度O(N) 空间复杂度O(N)
public int singleNumber(int[] nums) {HashMapInteger, 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 -1; // 这句不会执行
}
2. 位操作
2.1 一般思路
如果所有数字都出现了 3 次那么每一列的 1 的个数就一定是 3 的倍数。之所以有的列不是 3 的倍数就是因为只出现了 1 次的数贡献出了 1。所以所有不是 3 的倍数的列写 1其他列写 0 就找到了这个出现 1 次的数。
假如例子是 1 2 6 1 1 2 2 3 3 3, 3 个 1, 3 个 2, 3 个 3,1 个 6
1 0 0 1
2 0 1 0
6 1 1 0
1 0 0 1
1 0 0 1
2 0 1 0
2 0 1 0
3 0 1 1
3 0 1 1
3 0 1 1
看最右边的一列 1001100111 有 6 个 1
再往前看一列 0110011111 有 7 个 1
再往前看一列 0010000 有 1 个 1
我们只需要把是 3 的倍数的对应列写 0不是 3 的倍数的对应列写 1
也就是 1 1 0,也就是 6。
时间复杂度O(N) 空间复杂度O(1)
public int singleNumber(int[] nums) {int ans 0;//考虑每一位for (int i 0; i 32; i) {int count 0;//考虑每一个数for (int j 0; j nums.length; j) {//当前位是否是 1if ((nums[j] i 1) 1) {count;}}//1 的个数是否是 3 的倍数if (count % 3 ! 0) {ans ans | 1 i;}}return ans;
}
2.2 类似题目通用思路 二进制思想 详情逐步思路 位运算 判相等异或^ 取位与1 置位或|1
public int singleNumber(int[] nums) {int x1 0, x2 0, mask 0;for (int i : nums) {x2 ^ x1 i;x1 ^ i;mask ~(x1 x2);x2 mask;x1 mask;}return x1;
}
【总结】
1.Iterator的API
关于Iterator主要有三个方法hasNext()、next()、remove() hasNext:没有指针下移操作只是判断是否存在下一个元素 next指针下移返回该指针所指向的元素 remove删除当前指针所指向的元素一般和next方法一起用这时候的作用就是删除next方法返回的元素
2. HashMap
1 插入键值对数据 public V put(K key, V value) 2根据键值获取键值对值数据 public V get(Object key) 3获取Map中键值对的个数 public int size() 4判断Map集合中是否包含键为key的键值对 public boolean containsKey(Object key) 5判断Map集合中是否包含值为value的键值对 boolean containsValue(Object value) 6判断Map集合中是否没有任何键值对 public boolean isEmpty() 7清空Map集合中所有的键值对 public void clear() 8根据键值删除Map中键值对 public V remove(Object key)
遍历hashMap
for (Integer key : map.keySet()) { if (map.get(key) 1) {return key;}3. 扩展
对于 k 5, p 3 怎么做也就是每个数字出现了5 次只有一个数字出现了 3 次。 根据 k 5所以我们至少需要 3 个比特位。因为 2 个比特位最多计数四次。 根据 k 的二进制形式是 101所以 mask ~(x1 ~x2 x3)。 根据 p 的二进制是 011所以我们最后可以把 x1 返回。
public int singleNumber(int[] nums) {int x1 0, x2 0, x3 0, mask 0;for (int i : nums) {x3 ^ x2 x1 i;x2 ^ x1 i;x1 ^ i;mask ~(x1 ~x2 x3);x3 mask;x2 mask;x1 mask;}return x1;
}
转载链接https://leetcode.wang/leetcode-137-Single-NumberII.html
