我最近在接受采访时问他技术问题.一个是如何计算缺少长度为n-1的列表中的哪个数字.该列表包含从1到n的每个数字,除了i,其中1 <= i <= n.这些数字不合适.我的解决方案是将它们全部加起来,然后从1到n的数字的计算中减去它,通过将n加1并且适当地乘以n/2或(n-1)/ 2.但我觉得有一种更好的方法可以做到这一点.什么是最佳解决方案？
在我看来,你的答案已经足够好了.
但有些人 - 也许你的面试官就是其中之一 - 担心溢出等等.在这种情况下,使用XOR而不是添加.
要获得从0到n的整数的XOR,在循环时只需将数组索引进行异或.给定从0到n的整数的XOR,以及数组元素的XOR,您只需将其中的两个XOR混合在一起以获得缺少的元素.
PS从1到n的整数之和总是(n + 1)*n/2