漫画算法:找出缺失的整数

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%841

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%842

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%843

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%844

小灰一边回忆一边讲述起当时面试的情景……

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%951

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%952

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%953

题目:一个无序数组里有99个不重复正整数,范围从1到100,唯独缺少一个整数。如何找出这个缺失的整数?

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%954

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%955

解法一:

创建一个HashMap,以1到100为键,值都是0 。然后遍历整个数组,每读到一个整数,就找到HashMap当中对应的键,让其值加一。

由于数组中缺少一个整数,最终一定有99个键对应的值等于1, 剩下一个键对应的值等于0。遍历修改后的HashMap,找到这个值为0的键。

假设数组长度是N,那么该解法的时间复杂度是O(1),空间复杂度是O(N)。

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%956

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%954

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%957

解法二:

先把数组元素进行排序,然后遍历数组,检查任意两个相邻元素数值是否是连续的。如果不连续,则中间缺少的整数就是所要寻找的;如果全都连续,则缺少的整数不是1就是100。

假设数组长度是N,如果用时间复杂度为O(N*LogN)的排序算法进行排序,那么该解法的时间复杂度是O(N*LogN),空间复杂度是O(1)。

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%958

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%954

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%959

解法三:

很简单也很高效的方法,先算出1+2+3….+100的和,然后依次减去数组里的元素,最后得到的差,就是唯一缺失的整数。

假设数组长度是N,那么该解法的时间复杂度是O(N),空间复杂度是O(1)。

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%9510

题目扩展:一个无序数组里有若干个正整数,范围从1到100,其中99个整数都出现了偶数次,只有一个整数出现了奇数次(比如1,1,2,2,3,3,4,5,5),如何找到这个出现奇数次的整数?

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%954

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%9511

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%9512

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%9513

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%9514

解法:

遍历整个数组,依次做异或运算。由于异或在位运算时相同为0,不同为1,因此所有出现偶数次的整数都会相互抵消变成0,只有唯一出现奇数次的整数会被留下。

假设数组长度是N,那么该解法的时间复杂度是O(N),空间复杂度是O(1)。

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%9515

题目第二次扩展:一个无序数组里有若干个正整数,范围从1到100,其中98个整数都出现了偶数次,只有两个整数出现了奇数次(比如1,1,2,2,3,4,5,5),如何找到这个出现奇数次的整数?

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%9516

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%9517

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%9518

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%9519

解法:

遍历整个数组,依次做异或运算。由于数组存在两个出现奇数次的整数,所以最终异或的结果,等同于这两个整数的异或结果。这个结果中,至少会有一个二进制位是1(如果都是0,说明两个数相等,和题目不符)。

举个例子,如果最终异或的结果是5,转换成二进制是00000101。此时我们可以选择任意一个是1的二进制位来分析,比如末位。把两个奇数次出现的整数命名为A和B,如果末位是1,说明A和B转为二进制的末位不同,必定其中一个整数的末位是1,另一个整数的末位是0。

根据这个结论,我们可以把原数组按照二进制的末位不同,分成两部分,一部分的末位是1,一部分的末位是0。由于A和B的末位不同,所以A在其中一部分,B在其中一部分,绝不会出现A和B在同一部分,另一部分没有的情况。

这样一来就简单了,我们的问题又回归到了上一题的情况,按照原先的异或解法,从每一部分中找出唯一的奇数次整数即可。

假设数组长度是N,那么该解法的时间复杂度是O(N)。把数组分成两部分,并不需要借助额外存储空间,完全可以在按二进制位分组的同时来做异或运算,所以空间复杂度仍然是O(1)。

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%9520

十分钟后……

%e5%b0%8f%e4%bb%93%e9%bc%a0%e9%9d%a2%e8%af%9521

以上就是小灰面试的情况……

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%845

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%846

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%847

%e5%b0%8f%e4%bb%93%e9%bc%a0%e5%af%92%e6%9a%848

打赏支持我写出更多好文章,谢谢!

打赏作者

打赏支持我写出更多好文章,谢谢!

5 18 收藏 20 评论

关于作者:玻璃猫

互联网公司的码农一枚,喜欢算法和面向对象设计。个人微信号:13522239721 个人订阅号:dreamsee321欢迎一起交流讨论! 个人主页 · 我的文章 · 70 ·  

相关文章

可能感兴趣的话题



直接登录
最新评论
  • 王念一 初三学生 10/13

    结论:只会问问题的面试官都是*哔——*

  • ★小V★ 程序員 10/14

    根據漫畫的說法我把code寫出來了

    第一道那麼簡單我就不貼了...貼的是後面2道

    • ★小V★ 程序員 10/14

      可以無視,當時debug用忘了刪了lol

    • 玻璃猫 程序员 10/14

      代码写的非常好,谢谢分享!

    • 玻璃猫 程序员 10/14

      public static int findoutMissingDigits(int[] arr){
      int result = 0;
      for (int i : arr){
      result ^= i;
      }
      return result;
      }

      public static int[] findoutMissingDigits2(int[] arr){
      int A = 0;
      int B = 0;
      int result = findoutMissingDigits(arr);
      //从两个数的异或结果,获得数组分治的“分水岭”
      int shedNum = getShedNum(result);
      for (int i : arr){
      A = ((i& shedNum) == 0)? (A^i):A;
      B = ((i& shedNum) != 0)? (B^i):B;
      }
      return new int[]{A, B};
      }

      private static int getShedNum(int num){
      int numShift = 1;

      while((num & numShift) ==0){
      numShift = numShift<<1;
      }

      return numShift;
      }

      • 玻璃猫 程序员 10/14

        我这边在你的代码基础上也写了个试试,纯用位运算来拆分整个数组

  • 王念一 初三学生 10/14

    话说小灰这次居然拿到offer了……

    准备弃坑的节奏?

  • Tsingfeng   10/15

    为啥用hashmap的时间复杂度是O(1)? 虽然单次操作是O(1), 但是需要操作2n次啊

  • 小C   10/17

    题目第一次扩展时,题意不明。99个出现偶次,但没有指明顺序。比如:1,2,3,2,1。

  • 南山一叶 软件攻城狮 10/24

    第一次扩展的题目可以先求出1到100的和的两倍,然后再一个个减去数组的值,最后剩下的就是缺失的整数了。这种方法和异或那种更快呢?

  • White Java Developer 10/31

    最后一个问题似乎也可以有另外一种不错的算法.

    由于只有两个不同的奇数,那么 异或的可能值只有三个(A, B, A xor B).

    所以只要记录依次运算中得到的所有异或值,那么除去最后一个剩下的两个就是要求的数字了.

    如果只记录两个异或数值 那么应该是(A, A xor B)的形式, B也可以计算出来.

    这样的话,时间O(n) 空间(1)

    与文中最后的建议算法一样。

跳到底部
返回顶部