【技巧】Leetcode 137. 只出现一次的数字 II【中等】
只出现一次的数字 II
- 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
示例 1：
输入：nums = [2,2,3,2]
输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,99]
输出：99
解题思路
要找到一个整数数组中唯一出现一次的元素，其余元素都出现三次，我们可以使用位操作的方法。 这种方法利用了数字在计算机中是以二进制形式存储的特性，通过统计每一位上出现1的次数来解决这个问题。
- 使用32位整数来表示所有的数字。对于每一位，统计所有数字在这一位上出现1的次数。
- 由于其余每个元素都出现三次，如果某一位上1出现的次数不是3的倍数，那么那个只出现一次的数字在这一位上必然是1。
Java实现
public class SingleNumberII {public int singleNumber(int[] nums) {int[] bitCount = new int[32];// 统计每一位上1的出现次数for (int num : nums) {for (int i = 0; i < 32; i++) {
// (num & (1 << i)) 的含义
// 1 << i 将数字 1 的二进制表示左移 i 位，结果是一个只有第 i 位为1，其余位为0的数字。例如，1 << 2 的结果是 0100。
// (num & (1 << i)) 将 num 与这个只有第 i 位为1的数字进行与操作。这样我们就可以检查 num 在第 i 位是否为1。
// 如果结果不为0，说明 num 在第 i 位是1；否则为0。if ((num & (1 << i)) != 0) {bitCount[i]++;}}}int result = 0;for (int i = 0; i < 32; i++) {if (bitCount[i] % 3 != 0) {//还原数字，result | (1 << i) 将 result 的第 i 位设置为1（其他位保持不变）。result |= (1 << i);}}return result;}// 测试用例public static void main(String[] args) {SingleNumberII solution = new SingleNumberII();int[] nums1 = {2, 2, 3, 2};int[] nums2 = {0, 1, 0, 1, 0, 1, 99};System.out.println(solution.singleNumber(nums1)); // 期望输出: 3System.out.println(solution.singleNumber(nums2)); // 期望输出: 99}
}
时间空间复杂度
- 时间复杂度：O(n)，其中 n 是数组的长度。需要遍历数组每个数字，并对其32位进行统计。
- 空间复杂度：O(1)，虽然使用了一个长度为32的数组 bitCount，但它是常数级的，不随输入规模变化而变化。