O（n）的算法，找到失踪的整数 [英] O(n) algorithm, find the missing integer

问题描述

这是数组A有n-1独特的整数的范围是[0，N-1]，也就是说，有在此范围内，是不是在A.设计一个O（n）的算法发现，排名第一的数。只允许使用O（1）额外的空间除了数组A本身。

需要一些帮助这个问题，

解决方案

1. 总和的阵列。
2. 在使用等差数列公式计算预期的总和

根据这些数值：一个是 0 + 1 + 2 + ... + N-1 ，另一种是你的实际元素的总和 - 认为他们之间的区别彼此有什么做一件有其他没有。确保你知道，答案是微不足道的。

编辑：（理论评论）：
请注意，和（阵列）需要 2 * log_2（MAX（ARR））位。所以，如果你的元素都是32位整数，你将需要至少64位重新present的总和。 出租车从纯理论的方法 - 它不是 O（1）。但是，您可以使用数组本身（它包含更多的则 2 * log_2（MAX（ARR））位）来存储的总和。

An array A contains n-1 unique integers in the range [0, n-1], that is, there is one number from this range that is not in A. Design an O(n) algorithm for finding that number. Allowed to use only O(1) additional space besides the array A itself.

need some help for this question,

解决方案

1. Sum the array.
2. Calculate the expected sum using arithmetic progression formula

Given these values: one is 0 + 1 + 2 + ... + n-1, the other is the sum of your actual elements - think how they differ from each other, what does one have that the other does not. Make sure you know it, and the answer is trivial.

EDIT: (Theoretical comment):
Note that sum(array) needs 2*log_2(max(arr)) bits. So, if your elements are all 32 bits integers, you are going to need at most 64 bits to represent the sum.
From purely theoretical approach - it is NOT O(1). However, you can use the array itself (It contains more then 2*log_2(max(arr)) bits) to store the sum.

这篇关于O（n）的算法，找到失踪的整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！