137. Single Number II 「只出现一次的数字 II」

2020年04月01日 126点热度 0人点赞 2条评论

给定一个非空的整数数组,每个数字都出现次,只有一个数字例外只出现一次。找到那唯一的一个数字。

提示: 你的算法应当在线性时间复杂度内完成。你能不用额外空间来实现吗?

例一:
输入: [2,2,3,2]
输出: 3

例二:
输入: [0,1,0,1,0,1,99]
输出: 99

/*
 * 137. Single Number II
 * https://leetcode.com/problems/single-number-ii/
 * https://realneo.me/137-single-number-ii/
 */

public class SingleNumberII {
    public static void main(String[] args) {
        SingleNumberII solution = new SingleNumberII();

        int[] nums;
        nums = new int[]{2, 2, 3, 2};
        System.out.println(solution.singleNumber(nums));
        nums = new int[]{0, 1, 0, 1, 0, 1, 99};
        System.out.println(solution.singleNumber(nums));
    }

    public int singleNumber(int[] nums) {
        int seen1 = 0;
        int seen2 = 0;
        for (int num : nums) {
            seen1 = ~seen2 & (seen1 ^ num);
            seen2 = ~seen1 & (seen2 ^ num);
        }
        return seen1;
    }
}

参考链接:https://leetcode-cn.com/problems/single-number-ii/solution/single-number-ii-mo-ni-san-jin-zhi-fa-by-jin407891/

Neo

与卿再世相逢日,玉树临风一少年。

文章评论

  • aisaka

    这个思路有意思
    竟然用与或非性质

    2020年04月02日
    • Neo

      用逻辑运算来解决问题不少见,主要这个是用到了三进制的思想和状态机的想法,这我就想不出来了,还是参考的别人的思路才看明白

      2020年04月04日