在数组中查找缺失整数的最有效方法

Question

给定1到100的整数数组(随机插入),并从数组中取出一个整数.找到缺少的整数的最有效方法是什么？

Answer 1

如你所知整数,总算所有这些:

(1+N)*N/2 = (1+100)*100/2 = 5050

现在减去数组中的总和(S').差异将是您寻找的一个缺失的数字(所以x = 5050 - S').

时间复杂度为O(N),无法更快地解决,因为您肯定需要读取一次数组.