“给定一个数组,除了某个元素只出现一次,其他元素都出现三次,找出那个只出现一次的元素。”
题目链接:
来源:力扣(LeetCode)
链接: 137. 只出现一次的数字 II - 力扣(LeetCode)
给你一个整数数组 nums
,除某个元素仅出现 一次 外,其余每个元素都恰出现 三次 。 请你找出并返回那个只出现了一次的元素。
示例 1:
输入: nums = [2,2,3,2]
输出: 3
示例 2:
输入: nums = [0,1,0,1,0,1,99]
输出: 99
这道题没有空间复杂度的要求,可以使用Hash表来记录每个数字出现的次数,对于Hast表来说,键表示元素,值表示出现的次数。
在统计完成后,遍历一次Hash表即可找到只出现一次的元素
代码参考:
class Solution {
public int singleNumber(int[] nums) {
Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
int ans = 0;
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
int num = entry.getKey(), occ = entry.getValue();
if (occ == 1) {
ans = num;
break;
}
}
return ans;
}
}
时间复杂度:O(n)
其中n是数组的长度。
空间复杂度:O(n)
其中n是数组的长度,Hash表只需要O(n)的空间。
就本道题来说,实现不难,难的在于如何实现时间复杂度O(n)和空间复杂度O(1)。