logo
数字面试题
数字面试题

数字面试题

给定一个数组,包含从 1 到 N 所有的整数,但其中缺了两个数字,O(N) 时间内用 O(1) 的空间,找出来两个数字,
例如:
输入: [1]
输出: [2,3]
三个方法

01第一个就是数学 的方法

正整数数列求和 s1 = n(n+1)/2
平方和 s2 = n(n+1)(2n+1)/6
先算出期望的s1,s2,在遍历数组并在s1,s2中减去每项和它的平方,最后得到的就是,小时的两个数字的和以及它们的平方和,然后用一些简单的数学知识就能解出2数。
notion image

02第二个就是hash

若是题目没有要求O(1)空间,那么直观的想法就是新建一个size为nums.size()+2的新数组,然后遍历nums,将nums中的每个数字映射到新数组中下标 和每个数字相同的位置,然后遍历新数组,找到缺失的两个数字。
本章目录
    logo

    Follow Us

    linkedinfacebooktwitterinstagramweiboyoutubebilibilitiktokxigua

    We Accept

    /image/layout/pay-paypal.png/image/layout/pay-visa.png/image/layout/pay-master-card.png/image/layout/pay-airwallex.png/image/layout/pay-alipay.png

    地址

    Level 10b, 144 Edward Street, Brisbane CBD(Headquarter)
    Level 2, 171 La Trobe St, Melbourne VIC 3000
    四川省成都市武侯区桂溪街道天府大道中段500号D5东方希望天祥广场B座45A13号
    Business Hub, 155 Waymouth St, Adelaide SA 5000

    Disclaimer

    footer-disclaimerfooter-disclaimer

    JR Academy acknowledges Traditional Owners of Country throughout Australia and recognises the continuing connection to lands, waters and communities. We pay our respect to Aboriginal and Torres Strait Islander cultures; and to Elders past and present. Aboriginal and Torres Strait Islander peoples should be aware that this website may contain images or names of people who have since passed away.

    匠人学院网站上的所有内容,包括课程材料、徽标和匠人学院网站上提供的信息,均受澳大利亚政府知识产权法的保护。严禁未经授权使用、销售、分发、复制或修改。违规行为可能会导致法律诉讼。通过访问我们的网站,您同意尊重我们的知识产权。 JR Academy Pty Ltd 保留所有权利,包括专利、商标和版权。任何侵权行为都将受到法律追究。查看用户协议

    © 2017-2024 JR Academy Pty Ltd. All rights reserved.

    ABN 26621887572