首页 > 其他分享 >只出现一次的数字

只出现一次的数字

时间:2022-11-21 20:02:31浏览次数:48  
标签:一次 return 数字 nums int res mp 出现

题目描述

给你一个整数数组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

相关文章