在寻找失踪数组整数最有效的方法 [英] Most efficient way of finding missing integer in array

问题描述

鉴于整数1到100（随机插入）的阵列，以及一个整数取出的数组。什么是找到整数缺少的最有效方法是什么？

Given an array of integers 1 to 100 (inserted randomly), and one integer is taken out of the array. What is the most efficient way of finding the integer that is missing?

推荐答案

正如你所知道的整数，使所有这些的总和：

As you know the integers, make a sum of all of them:

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

现在substract那些数组中的总和（ S'的）。所不同的将是一个缺少一些你追求（让 X = 5050 - S'）。

时间复杂度为O（N），并不能得到解决得更快，因为你一定要读阵列一次。

Time complexity is O(N) and can't be solved faster, because you definitely need to read the array once.

这篇关于在寻找失踪数组整数最有效的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！