在时间 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)?

例如，4,1,2,3 的数组将变为 4,1,2,2.

For example, an array of 4,1,2,3 would become 4,1,2,2.

时间的简单解决方案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]; 创建第二个数组 bool B[N] 也是 bool=false 类型.迭代第一个数组并设置 B[A[i]]=true 如果为假，否则为 bing！

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屋！