只出现一次的数字 II
难度:
标签:
题目描述
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
示例 1：
输入：nums = [2,2,3,2] 输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,99] 输出：99
提示：
1 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1nums中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
代码结果
运行时间: 25 ms, 内存: 17.7 MB
/*
题目思路：
使用Java Stream API，我们可以利用stream的各种操作来解决这个问题。虽然直接使用Stream API解决这个问题不一定能保证O(1)的空间复杂度，但可以简化代码。
我们可以首先使用Map<Integer, Long>来统计每个数字出现的次数，然后找出那个只出现一次的数字。
*/
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
public class Solution {
public int singleNumber(int[] nums) {
Map<Integer, Long> frequency = Arrays.stream(nums)
.boxed()
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
return frequency.entrySet().stream()
.filter(entry -> entry.getValue() == 1)
.map(Map.Entry::getKey)
.findFirst()
.orElseThrow();
}
}解释
方法:
该题解采用位运算和计数的方法来找到只出现一次的元素。首先，创建一个长度为32的数组来统计每个整数的每一位上1出现的次数。接着，遍历输入数组，对每个数字，通过位运算统计其每一位的1的数量，并更新到计数数组中。由于除了一个元素之外，其他元素都出现三次，如果某位的计数能被3整除，则目标元素在该位为0；否则为1。最后，根据这些位的信息重构出只出现一次的数字。特别注意的是，对于32位整数的最高位（符号位），需要特殊处理，以区分正负数。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在位运算解法中，为什么选择32位整数数组来存储每一位的计数，而不是其他长度？
▷🦆
解法中提到的对最高位（符号位）的特殊处理是怎样的？为什么需要这样处理？
▷🦆
题解中提到，如果某位的计数能被3整除，则目标元素在该位为0；否则为1。这个逻辑是如何根据题目条件推导出来的？
▷相关问题
只出现一次的数字
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
输入：nums = [2,2,1] 输出：1
示例 2 ：
输入：nums = [4,1,2,1,2] 输出：4
示例 3 ：
输入：nums = [1] 输出：1
提示：
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- 除了某个元素只出现一次以外，其余每个元素均出现两次。
只出现一次的数字 III
给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
示例 1：
输入：nums = [1,2,1,3,2,5] 输出：[3,5] 解释：[5, 3] 也是有效的答案。
示例 2：
输入：nums = [-1,0] 输出：[-1,0]
示例 3：
输入：nums = [0,1] 输出：[1,0]
提示：
2 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1- 除两个只出现一次的整数外，
nums中的其他数字都出现两次