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

相关推荐

  • leetcode155-最小栈

    原题 设计一个支持 push,pop,top 操作,并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。 pop() – 删除栈顶的元素。 top() …

    算法 2019年12月11日
    0130
  • leetcode111-二叉树的最小深度

    原题 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,nul…

    算法 2020年3月25日
    0220
  • leetcode295-数据流的中位数

    原题 中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。 例如, [2,3,4] 的中位数是 3 [2,3] 的中位数是 (2 + 3) / 2 = 2.…

    算法 2020年2月12日
    0120
  • leetcode77-组合

    原题 给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。 示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], […

    算法 2020年5月12日
    0650
  • leetcode733-图像渲染

    原题 有一幅以二维整数数组表示的图画,每一个整数表示该图画的像素值大小,数值在 0 到 65535 之间。 给你一个坐标 (sr, sc) 表示图像渲染开始的像素值(行 ,列)和一…

    2019年12月13日
    0100
  • leetcode80-删除排序数组中的重复项II

    原题 给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素最多出现两次,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外…

    算法 2020年5月26日
    0140
  • 蓝桥杯试题-哈夫曼树

    原题 Description Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。 给出一列数{pi}={p0, p1, …, pn-1},用这列…

    算法 2020年3月1日
    0250
  • leetcode652-寻找重复的子树

    原题 给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。 两棵树重复是指它们具有相同的结构以及相同的结点值。 示例1: 1 / \ 2…

    算法 2019年12月26日
    0310
  • 使用递归函数逆序一个栈

    原题(来源:牛客网) 一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后,从栈顶到栈底为1,2,3,4,5,也就是实现了栈中元素的逆序,请设计…

    算法 2020年4月19日
    0250
  • leetcode234-回文链表

    原题 请判断一个链表是否为回文链表。 示例1: 输入: 1->2 输出: false 示例2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂…

    2019年12月16日
    0120

发表回复

登录后才能评论