137. 只出现一次的数字 II
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例1:
输入: [2,2,3,2]
输出: 3
示例2:
输入: [0,1,0,1,0,1,99]
输出: 99
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number-ii/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
-
1. map映射
思路：
方法类似于 LeetCode 136. 只出现一次的数字 - 简书
复杂度分析：
时间复杂度：O(n + m) = O(n), 时间复杂度为两次遍历所用的时间
空间复杂度：O(n), map所需要的空间
-
2. 排序法
思路：
- 先将数组进行排序
- 遍历该数组，判断当前元素和下一个元素是否相等，如果不等，返回该数即可，否则继续向下遍历
- 如果遍历到最后一个元素还没有找到出现一次的数字，则最后一个元素一定是我们需要的
public static int singleNumber(int[] nums) {
Arrays.sort(nums);
for (int i = 0; i < nums.length; i += 3) {
if (i == nums.length - 1) return nums[i];
if (nums[i] != nums[i + 1]) return nums[i];
}
return -1;
}
复杂度分析：
时间复杂度：O(n)
空间复杂度：O(1)
-
3. 计数法
思路：使用(set去重后的元素之和 * 3 - 原数组之和) / 2 则为不重复的元素
public static int singleNumber(int[] nums) {
Set<Integer> set = new TreeSet<>();
int sum = 0;
int setSum = 0;
for (int num : nums) {
sum += num;
set.add(num);
}
for (Integer i : set) {
setSum += i;
}
return (setSum * 3 - sum) / 2;
}
复杂度分析：
时间复杂度：O(n + s), 遍历数组和set所需的时间
空间复杂度：O(n), set所需的空间
-
测试用例
public static void main(String[] args) {
int[] nums = {2, 2, 3, 2};
System.out.println(Arrays.toString(nums));
System.out.println("只出现一次的数字 II:" + singleNumber2(nums));
}
-
结果
[2, 2, 3, 2]
只出现一次的数字 II:3
-
源码
-
我会每天更新新的算法，并尽可能尝试不同解法，如果发现问题请指正
- Github
