查找数组中重复的元素在时间为O（n） [英] Find duplicate element in array in time O(n)

问题描述

我一直在问这个问题在面试中，我一直想知道正确的答案。

I have been asked this question in a job interview and I have been wondering about the right answer.

您有号码的从0到n-1，这些数字中的一个被除去，这使得该号码的复本阵列中已经替换为编号的数组。我们如何可以检测到这种重复的时间的 O（N）的？

You have an array of numbers from 0 to n-1, one of the numbers is removed, and replaced with a number already in the array which makes a duplicate of that number. How can we detect this duplicate in time O(n)?

例如，数组 1,2,3,4 将成为 1,2,2,4- 。

时的简单的解决方案的为O（n ² ）的是使用嵌套循环去寻找每个元素的副本。

The easy solution of time O(n²) is to use a nested loop to look for the duplicate of each element.

推荐答案

我们有原来的数组 INT A [N]; 创建第二个阵列布尔B〔N] 太，类型布尔=假。迭代的第一阵列，​​并设置 B [A [1] = TRUE ，如果是假的，否则兵！

We have the original array int A[N]; Create a second array bool B[N] too, of type bool=false. Iterate the first array and set B[A[i]]=true if was false, else bing!

这篇关于查找数组中重复的元素在时间为O（n）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！