题目描述
给你一个整数数组nums,除某个元素仅出现一次外,其余每个元素都恰出现三次。请你找出并返回那个只出现了一次的元素。
示例 1:
输入:nums = [2,2,3,2]
输出:3
示例 2:
输入:nums = [0,1,0,1,0,1,100]
输出:100
提示:
1 <= nums.length <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1
nums 中,除某个元素仅出现一次外,其余每个元素都恰出现三次
思路一:暴力求解
对数组直接排序,如果相邻两个相等,就让下标走3步,不相等直接返回,遍历结束如果还没返回,说明是最后一个元素,直接返回最后一个元素
public int singleNumber1(int[] nums) {
Arrays.sort(nums);
int res = 0;
for (int i = 0; i < nums.length - 1; ) {
if (nums[i] == nums[i + 1]) {
res = nums[i];
i += 3;
} else {
return nums[i];
}
}
return nums[nums.length - 1];
}
思路二:利用map,统计每个数字出现次数,最后在遍历输出出现一次的数
public int singleNumber2(int[] nums) {
Map<Integer, Integer> mp = new HashMap<>();
for (int i : nums) {
mp.put(i, mp.getOrDefault(i, 0) + 1);
}
for (Map.Entry<Integer, Integer> e : mp.entrySet()) {
if (e.getValue() == 1) {
return e.getKey();
}
}
return -1;
}
思路三:位运算。数组中出现的数字都是3次,只有一个出现一次,所以把数组中的每位的数mod3剩下的就是出现一次的数字。每位找到之后按位放到返回值中即可。
public int singleNumber(int[] nums) {
int tmp = 0;
int res = 0;
for (int i = 0; i < 32; i++) {
for (int j : nums) {
// 统计一趟每个二进制位之和
tmp += (j >> i) & 1;
}
if (tmp % 3 != 0) {
// 异或操作:就是将二进制位按原来数字二进制复位
res |= (1 << i);
}
tmp = 0;
}
return res;
}
标签:一次,return,数字,nums,int,res,mp,出现
From: https://www.cnblogs.com/du001011/p/16912997.html