leetcode260-只出现一次的数字III

原题

给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例:

输入: [1,2,1,3,2,5] 输出: [3,5]

注意:

  1. 结果输出的顺序并不重要,对于上面的例子, [5, 3] 也是正确答案。
  2. 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?

解法

思想

如果不限制常数空间复杂度用哈希表计数可以很容易做出来,但是限制了空间复杂度,可以用位运算:

只看题目,和leetcode136-只出现一次的数字很相似,对于唯一一个只出现一次的数字,我们可以通过异或将其找出,这道题有两个只出现一次的数字,如果将所有的数字异或,结果并不能显示是哪两个数字只出现一次。可以想办法将这些数字分为两组,并将两个不同的数字分到不同的组中,再进行查找。

那么如何将两个不同的数字分到两个不同的组中呢,可以使用第一次将全部数字异或的结果,得到的结果其实就是这两个数字异或的结果。因为这两个数字不一样,得到的异或结果也必定有至少一位是1。只要将这一位是1的数字分为一组,是0的数字分为一组,就能将所有数字分为两组,而这两组中只有一个只出现一次的数字,异或的结果就是这个数字。

代码

class Solution {
    public int[] singleNumbers(int[] nums) {
        int k = 0;
        for(int num: nums) {
            k ^= num;
        }
        int mask = 1;

        //找到k中最靠近低位的1
        while((k & mask) == 0) {
            mask <<= 1;
        }

        int a = 0;
        int b = 0;

        //使用掩码进行与运算,结果是0分为一组,结果是1分为一组
        for(int num: nums) {
            if((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }

        return new int[]{a, b};
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode260-%e5%8f%aa%e5%87%ba%e7%8e%b0%e4%b8%80%e6%ac%a1%e7%9a%84%e6%95%b0%e5%ad%97iii/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月27日 23:16
下一篇 2020年4月28日 22:58

相关推荐

  • leetcode1115-交替打印FooBar

    原题 我们提供一个类: class FooBar { public void foo() {     for (int i = 0; i < n; i++) {       …

    算法 2020年2月2日
    0180
  • 剑指offer40-最小的k个数

    原题(来源Leetcode) 输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。 示例 1: …

    算法 2020年3月20日
    0390
  • 剑指offer46-把数字翻译成字符串

    原题 给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编…

    算法 2020年2月29日
    0300
  • 蓝桥杯试题-翻硬币

    原题 资源限制 时间限制:1.0s 内存限制:256.0MB 问题描述 小明正在玩一个“翻硬币”的游戏。 桌上放着排成一排的若干硬币。我们用 * 表示正面,用 o 表示反面(是小写…

    算法 2020年3月1日
    0140
  • 二叉树中序遍历-折纸问题

    原题(来源牛客网) 请把纸条竖着放在桌⼦上,然后从纸条的下边向上⽅对折,压出折痕后再展开。此时有1条折痕,突起的⽅向指向纸条的背⾯,这条折痕叫做“下”折痕 ;突起的⽅向指向纸条正⾯…

    2020年4月27日
    02660
  • leetcode73-矩阵置零

    原题 给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1: 输入: [   [1,1,1],  …

    算法 2020年5月14日
    0100
  • leetcode429-N叉树的层序遍历

    原题 给定一个 N 叉树,返回其节点值的层序遍历。 (即从左到右,逐层遍历)。 例如,给定一个 3叉树 : 返回其层序遍历: [ [1], [3,2,4], [5,6] ] 说明:…

    2020年1月20日
    0140
  • leetcode62-不同路径

    原题 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Fi…

    2020年2月21日
    0370
  • leetcode136-只出现一次的数字

    原题 给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗…

    算法 2019年12月18日
    0150
  • leetcode380-常数时间插入、删除和获取随机元素

    原题 设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构。 insert(val):当元素 val 不存在时,向集合中插入该项。 remove(val):元素 v…

    2019年12月28日
    0100

发表回复

登录后才能评论