给定一个整数数组,数组中有一个数出现了一次,其他数出现了三次,请找出只出现了一次的数。
数据范围:数组大小满足 ,数组中每个元素大小满足
object Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型 */ def singleNumber(nums: Array[Int]): Int = { // write code here nums.map((_, 1)).groupBy(_._1).mapValues(_.size).toArray.sortBy(_._2)(Ordering[Int])(0)._1 } }
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @return int整型 */ public int singleNumber (int[] nums) { // write code here int[] t = new int[32]; for(int num: nums){ for(int i = 0; i < 32; i++){ t[i] += (num >> i) & 1; } } int ans = 0; for(int i = 0; i < 32; i++){ if(t[i] % 3 == 1){ ans |= (1 << i); } } return ans; } }
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int singleNumber(vector<int>& nums) { // write code here int result=0; for(int i=0;i<32;i++) { int total=0; for(int num:nums) { total+=(num>>i)&1; } if(total%3) { result|=(1<<i); } } return result; } };
方法1:排序
import java.util.*; public class Solution { public int singleNumber (int[] nums) { Arrays.sort(nums); int n = nums.length; for(int i = 0; i < n;){ if(i < n - 1 && nums[i] == nums[i + 1]){ while(i < n - 1 && nums[i] == nums[i + 1]){ i++; } }else{ return nums[i]; } i++; } return -1; } }
方法2:哈希表
import java.util.*; public class Solution { public int singleNumber (int[] nums) { Map<Integer,Integer> map = new HashMap<>(); int n = nums.length; for(int i = 0; i < n; i++){ map.put(nums[i],map.getOrDefault(nums[i],0) + 1); } for(int key: map.keySet()){ if(map.get(key) == 1){ return key; } } return -1; } }
方法3:位运算
import java.util.*; public class Solution { public int singleNumber (int[] nums) { int[] bitNum = new int[32]; int n = nums.length; for(int i = 0; i < 32; i++){ int mask = 1 << i; for(int j = 0; j < n; j++){ if((nums[j] & mask) == mask){ bitNum[i]++; } } } int res = 0; for(int i = 0; i < 32; i++){ if(bitNum[i] % 3 != 0){ res |= (1 << i); } } return res; } }
public class Solution { // 精简算法,位运算32位依次右移记录,遇到模3不为0就证明存在 // 此时加到res上,记得也要左移保证累加的位增大就好! public int singleNumber (int[] nums) { int cnt = 0, res = 0; for (int i = 0; i < 32; i++) { cnt = 0; for (int n : nums) { cnt += n >> i & 1; } res += (cnt % 3) << i; } return res; } }