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

相关推荐

  • leetcode167-两数之和II-输入有序数组

    原题 给定一个已按照 升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。 函数应该返回这两个下标值index1和index2,其中index1必须小于index2。 说明…

    算法 2019年11月20日
    0190
  • 剑指offer62-圆圈中最后剩下的数字

    原题(来源Leetcode) 0,1,,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 例如,0、1、2、3、4这5…

    算法 2020年3月30日
    0650
  • leetcode210-课程表II

    原题 现在你总共有 n 门课需要选,记为 0 到 n-1。 在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0…

    算法 2020年5月17日
    0130
  • leetcode124-二叉树中的最大路径和

    原题 给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入: [1…

    算法 2020年4月26日
    0170
  • leetcode1300-转变数组后最接近目标值的数组和

    原题 给你一个整数数组 arr 和一个目标值 target ,请你返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近 targe…

    算法 2020年6月14日
    0970
  • leetcode1103-分糖果II

    原题 排排坐,分糖果。 我们买了一些糖果 candies,打算把它们分给排好队的 n = num_people 个小朋友。 给第一个小朋友 1 颗糖果,第二个小朋友 2 颗,依此类…

    算法 2020年3月5日
    0140
  • leetcode636-函数的独占时间

    原题 给出一个非抢占单线程CPU的 n 个函数运行日志,找到函数的独占时间。 每个函数都有一个唯一的 Id,从 0 到 n-1,函数可能会递归调用或者被其他函数调用。 日志是具有以…

    算法 2020年2月2日
    0190
  • leetcode724-寻找数组的中心索引

    原题 给定一个整数类型的数组nums,请编写一个能够返回数组“中心索引”的方法。 我们是这样定义数组中心索引的:数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。 如果数…

    算法 2019年11月13日
    0140
  • 用一个栈实现另一个栈的排序

    原题(来源牛客网) 一个栈中元素的类型为整型,现在想将该栈从顶到底按从大到小的顺序排序,只许申请一个栈。除此之外,可以申请新的变量,但不能申请额外的数据结构。如何完成排序? 解法 …

    算法 2020年4月20日
    02110
  • leetcode367-有效的完全平方数

    原题 给定一个正整数 num,编写一个函数,如果 num 是一个完全平方数,则返回 True,否则返回 False。 说明: 不要使用任何内置的库函数,如  sqrt。 示例1: …

    算法 2020年1月5日
    0150

发表回复

登录后才能评论