IT大厂面试题目——如何在数组里快速定位唯一“落单”的数字?
数组问题和二分法问题一样,是互联网公司技术岗面试中很常见的考点。我在上一篇文章中分享了二分法问题的解答思路,指路我的文章 《IT大厂面试经验分享 —— 二分法》。
给第一次看文章的小伙伴介绍下自己~ 我在ACM/ICPC比赛中拿过亚洲区金牌,现在是TMD(今日头条,美团,滴滴)中一家的资深工程师,面试过上百位候选人。
话不多说,今天我来分享一道数组题目和解答思路:
“如何高效地在一个有大量重复数字的数组里,找到那个唯一落单的数字?”
举个栗子:. 一个数组里面大部分数出现的次数都是偶数次,有且仅有一个数只出现一次,能否用 O(1) 的时间复杂度将这个落单的数找出来。如 [1,2,3,1,2] 里找出 3 是落单的数。
关于这个问题,其实是有不少技巧性的,不同的算法模型,效率相差很多,当面试时遇到这类的问题,如何在面试官心中拿到高分。一起来看看吧。
60分的答案
利用排序算法将相同的数靠在一起,落单的数就是那个既和左边不一样,也和右边不一样的数。
时间复杂度:排序算法复杂度
面试官 OS:没有利用“偶数次”这个条件,速度比最优算法慢上不少。
80分的答案
了解位运算,能发现异或操作与偶数次的联系,将所有数都异或一遍就能得到落单的数
时间复杂度:O(n)
面试官 OS:思路敏捷,可造之材,不过考验才刚刚开始,现在题目稍微改一下,有两个数落单了,能把它们都找出来吗?
面试官加大题目的难度,既是挑战,同时也是巨大的机遇!
90分以上的答案
了解异或操作的本质,利用所有数的异或结果,得知这两个落单的数不同位是哪些,按某一个不同位,将数组分成两份,将问题退化至两个找“唯一落单”的问题,得到答案。
有点小复杂?下面举个栗子说明:
例:假设落单的数是 2 和 3, 2 的二进制 10, 3 的二进制 11, 异或的结果是 01,就可以知道两个落单的数第一位不一样,然后将数组按第一位是 0, 第一位是 1 分成两个数组,2 和 3 自然就分开了,再分别异或两个数组的所有数,就能得到 2 和 3。
今天分享到这里,喜欢我的文章的小伙伴关注我吧~ 我在牛客每周分享一道面试题,助你斩获大厂Offer!
作者:私坊茶话
链接:https://www.nowcoder.com/discuss/441858?channel=0&source_id=home_feed
来源:牛客网
看似最简单的问题,不同的回答却高下立判。现在总结出来的高分答案,都是当年求职一步一个坑摸索出来的血泪之谈。
我们团队成员都是来自
国内外科技大厂的资深工程师
毕业于全球Top30、国内Top5高校
当年均OFFER拿到手软
混迹于科技圈多年
现均为各领域专家、团队负责人
掌握着专项领域最前沿技术
积累了丰富的工作与求职经验
能给予你最透彻的解析