lc137. 只出现一次的数字 II-Toy模板网

这篇具有很好参考价值的文章主要介绍了lc137. 只出现一次的数字 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

lc137. 只出现一次的数字 II,排序算法,算法,数据结构

数组排序，既和前不一样又和后不一样的就是唯一的一个

    public static int numberOnce(int[] nums) {
        Arrays.sort(nums);
        if (nums.length > 2 && nums[0] != nums[1]) {//避免只有一个元素的数组
            return nums[0];
        }
        if (nums.length > 2 && nums[nums.length - 2] != nums[nums.length - 1]) {
            return nums[nums.length - 1];
        }
        for (int i = 1; i < nums.length - 1; i++) {
            if (nums[i] != nums[i - 1] && nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[0];//只有一个元素的数组
    }

哈希表

lc137. 只出现一次的数字 II,排序算法,算法,数据结构

位运算

lc137. 只出现一次的数字 II,排序算法,算法,数据结构

只有一个数出现了一次，其他数都出现了三次，那么别的数的每个二进制位加起来的和除3一定为0。

所以如果某个二进制位取余3不为0那么这个数就是所要求的答案的某个二进制位，再把它导出来加起来就得到答案。

lc137. 只出现一次的数字 II,排序算法,算法,数据结构

力扣每日一题：137. 只出现一次的数字 II（C++） - 知乎 (zhihu.com)

一些符号解释

(num >> i) & 1是将num左移i位进行按位与，即为保留num的第i位，其余位置零

如果num的第i位为0，则(num >> i) & 1的值为0，否则不为0

|= 按位或赋值运算符

按位或赋值运算符使用两个操作数的二进制表示，对它们执行按位或运算并将结果分配给变量

x |= y // x = x | y

与运算：针对补码进行运算

lc137. 只出现一次的数字 II,排序算法,算法,数据结构

    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            for (int num: nums) {
                //将每个二进制位加一起
                total += ((num >> i) & 1);//保留num的第i位，其余位为0，对于每个元素的第i位进行相加
            }
            if (total % 3 != 0) {//是否整除3，即为是否是所求的数
                ans |= (1 << i);//1 << i表示将1左移i位
                //ans = ans | (1 << i) 将二进制还原为十进制数
            }
        }
        return ans;
    }

代码

import org.junit.Test;
import java.util.Arrays;

public class NumberOnce {
    @Test
    public void test() {
        int[] nums = new int[]{2, 2, 3, 2};
        System.out.println(numberOnce(nums));
        int[] nums1 = new int[]{0,1,0,1,0,1,99};
        System.out.println(numberOnce(nums1));
        System.out.println(singleNumber(nums1));
    }

    public static int numberOnce(int[] nums) {
        Arrays.sort(nums);
        if (nums.length > 2 && nums[0] != nums[1]) {//避免只有一个元素的数组
            return nums[0];
        }
        if (nums.length > 2 && nums[nums.length - 2] != nums[nums.length - 1]) {
            return nums[nums.length - 1];
        }
        for (int i = 1; i < nums.length - 1; i++) {
            if (nums[i] != nums[i - 1] && nums[i] != nums[i + 1]) {
                return nums[i];
            }
        }
        return nums[0];//只有一个元素的数组
    }

    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            for (int num: nums) {
                //将每个二进制位加一起
                total += ((num >> i) & 1);//保留num的第i位，其余位为0，对于每个元素的第i位进行相加
            }
            if (total % 3 != 0) {//是否整除3，即为是否是所求的数
                ans |= (1 << i);//1 << i表示将1左移i位
                //ans = ans | (1 << i) 将二进制还原为十进制数
            }
        }
        return ans;
    }

}

文章来源地址https://www.toymoban.com/news/detail-645001.html

到了这里，关于lc137. 只出现一次的数字 II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！