LeetCode SingleNumber I,II,III

136. Single Number


Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

题目大意:一个数组中只有一个数字只出现一次,其他的都出现两次,求这个只出现一次的数字

class Solution {
     public int singleNumber(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            int x = 0;
            for (int i = 0; i < nums.length ;i++){
                x = x^nums[i];
            }
            return x;
        }
}

由于,异或运算支持交换律和结合律,所以,只要是出现次数为偶数次的数字,采用异或运算,结果为0;如此一来,如果数组中的一个数字只出现一次,那么最后的异或运算的结果就是这个数字。

137. Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

题目大意:只有一个数字是出现一次,其他的数字都是出现三次。

class Solution {
   public int singleNumber(int[] nums) {
        int a = 0;
        int b = 0;
        for (int n : nums) {
            a = (a^n) & (~b);
            b = (b^n) & (~a);
        }
        return a;
    }
    
}

数组为[2,2,2,3],一共有四个元素,进行四次循环。

第一次循环,b=(0000^0010)&1111=0010=2,a=(0000^0010)&1101=0000=0

第二次循环,b=(0010^0010)&1111=0000=0,a=(0000^0010)&1111=0010=2

第三次循环,b=(0000^0010)&1101=0000=0,a=(0010^0010)&1111=0000=0

第四次循环,b=(0000^0011)&1111=0011=3,a=(0000^0011)&1100=0000=0

 如果是出现两次的话,用一个bit就可以
    比如 b,初始为0
    当5第1次出现时, b=5
    当5第2次出现是, b清空为0,表示b可以去处理其他数字了
    所以,最后 如果 b !=0的话,b记录的就是只出现了一次的那个数字
    
    ->公式就是 b = b xor i  或者 b = b^i


    那么,如果是三次的话,香浓定理,需要用2bits进行记录

    当5第一次出现的时候,b = 5, a=0,  b记录这个数字
    当5第二次出现的时候,b = 0, a=5, a记录了这个数字
    当5第三次出现的时候,b = 0, a=0, 都清空了,可以去处理其他数字了
    所以,如果有某个数字出现了1次,就存在b中,出现了两次,就存在a中,所以返回 a|b

    公式方面 ,上面两次的时候,b清空的公式是 b = b xor i
            而第三次时,b要等于零,而这时a是True,所以再 & 一个a的非就可以,b = b xor & ~a
    -> b = b xor i & ~ a
       a = a xor i & ~b

260. Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

Example:

Input:  [1,2,1,3,2,5]
Output: [3,5]

Note:

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
public int[] singleNumber(int[] nums) {
       int x = 0;
        for ( int num :nums){
            x = x ^num;
        }
        int [] res = new int[2];
        int n = x & -x;
        for (int i = 0 ; i <nums.length;i++){
            if ((n & nums[i]) !=0){
                res[0] ^= nums[i];
            }else {
                res[1] ^= nums[i];
            }
        }
        return res;
    }
  1. 先将所有的数字进行异或运算,那么得到的结果就是这两个数字的异或运算结果,并且结果不为0
  2. 找到上述结果中的某个为1的位,那么,根据整个数组中这一位是1还是0,分为两个数组,第一个数组:这一位为0的数(包括重复的数和单独的一个数),第二个数组:这一位为1的数(包括重复的数和另一个单独的一个数)
  3. 对这两组数分别全部异或运算处理,那么得到的两个结果就是这两个单独的数

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-179-Largest Number(理解规则,自定义cmp函数进行排序)

1、这道题给定一个vector,里面存放着int类型的非负整数,要求把这些非负整数拼起来,尽可能拼成一个最大的整数。

20130
来自专栏用户2442861的专栏

JavaScript 正则表达式上——基本语法

JavaScript种正则表达式有两种定义方式,定义一个匹配类似 <%XXX%> 的字符串

7210
来自专栏偏前端工程师的驿站

JS魔法堂:再识Number type

Brief                                   本来只打算理解JS中0.1 + 0.2 == 0.300000000000000...

23550
来自专栏jessetalks

Javascript基础回顾 之(一) 类型

  本来是要继续由浅入深表达式系列最后一篇的,但是最近团队突然就忙起来了,从来没有过的忙!不过喜欢表达式的朋友请放心,已经在写了:) 在工作当中发现大家对Jav...

38170
来自专栏技术博客

C#基础知识系列十(集合)

  本节主要是来了解学习集合,以方便在程序编写时,什么地方该选用什么集合,让程序更健壮的运行起来。在学习了解集合之前,首先需要了解一些数据结构方面的知识。下面我...

12930
来自专栏mathor

ST算法

 RMQ(Range Minimum/Maximum Query),即区间最值查询。对于长度为n的数列arr,回答若干询问Q(i,j),返回数列arr中下标在i...

23320
来自专栏函数式编程语言及工具

Scalaz(12)- Monad:再述述flatMap,顺便了解MonadPlus

  在前面的几篇讨论里我们初步对FP有了些少了解:FP嘛,不就是F[A]吗?也是,FP就是在F[]壳子(context)内对程序的状态进行更改,也就是在F壳子(...

20170
来自专栏大数据风控

R中字段抽取、字段合并、字段匹配

1、字段抽取 字段抽取,是根据已知列数据的开始和结束位置,抽取出新的列 字段截取函数:substr(x,start,stop) tel <- '1892225...

92590
来自专栏Fish

内存对齐(Memory Alignment)

最近读文档,发现对内存对齐的概念不太明白。 内存对齐的原则: 数据成员对齐规则:结构(struct)(或联合(union))的数据成员,第一个数据成员放在o...

198100
来自专栏HansBug's Lab

1798: [Ahoi2009]Seq 维护序列seq

1798: [Ahoi2009]Seq 维护序列seq Time Limit: 30 Sec  Memory Limit: 64 MB Submit: 2930...

31150

扫码关注云+社区

领取腾讯云代金券