在整数数组中查找重复项 [英] Find a duplicate in array of integers

问题描述

这是一个面试问题。

我得到了一个范围为 n + 1 个整数的数组 [1，n] 。数组的属性是它具有 k（k> = 1）个重复项，每个重复项可以出现两次以上。我们的任务是找到在最佳时间和空间复杂度下多次出现的数组元素。

I was given an array of n+1 integers from the range [1,n]. The property of the array is that it has k (k>=1) duplicates, and each duplicate can appear more than twice. The task was to find an element of the array that occurs more than once in the best possible time and space complexity.

经过艰苦奋斗之后，我自豪地提出了<$占用 O（1）空间的c $ c> O（nlogn）解决方案。我的想法是将范围 [1，n-1] 分为两半，并确定两半中的哪一个包含来自输​​入数组的更多元素（我使用的是Pigeonhole原理）。该算法将递归地继续执行，直到达到间隔 [X，X] ，其中 X 出现两次，并且重复一次。

After significant struggling, I proudly came up with O(nlogn) solution that takes O(1) space. My idea was to divide range [1,n-1] into two halves and determine which of two halves contains more elements from the input array (I was using Pigeonhole principle). The algorithm continues recursively until it reaches the interval [X,X] where X occurs twice and that is a duplicate.

面试官很满意，但随后他告诉我，存在 O（n）解决方案，该方案具有恒定的空间。他慷慨地提供了一些提示（与排列有关的东西吗？），但是我不知道如何提出这样的解决方案。假设他没有撒谎，有人可以提供指导吗？我搜索了SO，发现此问题很少（更轻松）的变化，但不是这个特定问题。谢谢。

The interviewer was satisfied, but then he told me that there exists O(n) solution with constant space. He generously offered few hints (something related to permutations?), but I had no idea how to come up with such solution. Assuming that he wasn't lying, can anyone offer guidelines? I have searched SO and found few (easier) variations of this problem, but not this specific one. Thank you.

编辑：为了使事情更复杂，面试官提到不应修改输入数组。

In order to make things even more complicated, interviewer mentioned that the input array should not be modified.

推荐答案

1. 采用最后一个元素（x）。

1. Take the very last element (x).

将元素保存在位置x（y）。

Save the element at position x (y).

如果x == y，则发现重复项。

If x == y you found a duplicate.

用x覆盖位置x。

分配x = y并继续执行步骤2。

Assign x = y and continue with step 2.

您基本上是在对数组进行排序，这是可能的，因为您知道必须在哪里插入元素。 O（1）额外空间和O（n）时间复杂度。您只需要小心索引，为简单起见，我假设第一个索引在这里为1（而不是0），因此我们不必做+1或-1。

You are basically sorting the array, it is possible because you know where the element has to be inserted. O(1) extra space and O(n) time complexity. You just have to be careful with the indices, for simplicity I assumed first index is 1 here (not 0) so we don't have to do +1 or -1.

编辑：不修改输入数组

此算法基于以下思想：我们必须找到置换循环的入口点，那么我们还发现了一个重复项（为简单起见，还是基于1的数组）：

This algorithm is based on the idea that we have to find the entry point of the permutation cycle, then we also found a duplicate (again 1-based array for simplicity):

示例：

2 3 4 1 5 4 6 7 8

条目：8 7 6

置换周期：4 1 2 3

Permutation cycle: 4 1 2 3

我们可以看到重复项（4）是第一个

As we can see the duplicate (4) is the first number of the cycle.

1. 查找置换周期

1. Finding the permutation cycle

1. x =最后一个元素


2. x =位置x


3. 重复步骤2。n次（总共）保证我们进入周期

测量周期长度

Measuring the cycle length

1. a =上方的最后x个，b = la从上方看st x，计数器c = 0


2. a =位置a处的元素，b =位置b处的元素，b =位置b处的元素，c ++（所以我们向前走了2步b和1在循环中向前移动a）


3. 如果a == b，循环长度为c，否则继续执行步骤2。

找到循环的入口点

Finding the entry point to the cycle

1. x =最后一个元素


2. x =位置x处的元素


3. 重复步骤2。c次（总计）


4. y =最后元素


5. 如果x == y，则x是一个解（x进行了一个完整的周期，而y即将进入该周期）


6. x =位置x上的元素，y =位置y上的元素


7. 重复步骤5和6.，直到找到一个解决方案。

1. x = last element
2. x = element at position x
3. repeat step 2. c times (in total)
4. y = last element
5. if x == y then x is a solution (x made one full cycle and y is just about to enter the cycle)
6. x = element at position x, y = element at position y
7. repeat steps 5. and 6. until a solution was found.

这三个主要步骤都是O（n）和顺序的，因此总体复杂度也是O（n），空间复杂度是O（ 1）。

The 3 major steps are all O(n) and sequential therefore the overall complexity is also O(n) and the space complexity is O(1).

上面的示例：

1. x取以下值：8 7 6 4 1 2 3 4 1 2

1. x takes the following values: 8 7 6 4 1 2 3 4 1 2

a取以下值：2 3 4 1 2

b取以下值：2 4 2 4 2

因此c = 4（是的，有5个数字，但是c仅在执行步骤时才增加，而不是最初时）

a takes the following values: 2 3 4 1 2
b takes the following values: 2 4 2 4 2
therefore c = 4 (yes there are 5 numbers but c is only increased when making steps, not initially)

x采用以下值：8 7 6 4 | 1 2 3 4

y采用以下值： 8 7 6 4

x == y == 4最后是一个解决方案！

x takes the following values: 8 7 6 4 | 1 2 3 4
y takes the following values: | 8 7 6 4
x == y == 4 in the end and this is a solution!

注释中要求的示例2： 3 1 4 6 1 2 5

Example 2 as requested in the comments: 3 1 4 6 1 2 5

1. 输入周期：5 1 3 4 6 2 1 3

1. Entering cycle: 5 1 3 4 6 2 1 3

测量周期长度：

a：3 4 6 2 1 3

b：3 6 1 4 2 3

c = 5

Measuring cycle length:
a: 3 4 6 2 1 3
b: 3 6 1 4 2 3
c = 5

查找入口点：< br>
x：5 1 3 4 6 | 2 1

y：| 5 1

x == y == 1是一个解决方案

Finding the entry point:
x: 5 1 3 4 6 | 2 1
y: | 5 1
x == y == 1 is a solution

这篇关于在整数数组中查找重复项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！