在时间O(n)中查找数组中的重复元素

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

我在一次面试中被问到这个问题，我一直在想正确的答案。

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)?

你有一个从0到n-1的数组，其中一个数字被删除了，然后用一个已经在数组中的数字替换，这个数字复制了这个数字。我们如何能在时间O(n)中检测到这一副本?

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

例如，1、2、3、4的数组将变成1、2、2、4。

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

时间O(n2)的简单解决方案是使用一个嵌套循环来查找每个元素的副本。

20 个解决方案

#1

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!

我们有原始数组int A[N];创建第二个数组bool B[N]，类型bool=false。迭代第一个数组并设置B[i] =true if是false，否则bing!

#2

This can be done in O(n) time and O(1) space.

这可以在O(n)时间和O(1)空间中完成。

(The algorithm only works because the numbers are consecutive integers in a known range):

(该算法只起作用，因为数字是已知范围内的连续整数):

In a single pass through the vector, compute the sum of all the numbers, and the sum of the squares of all the numbers.

在一个单遍历向量中，计算所有数字的和，以及所有数字的平方和。

Subtract the sum of all the numbers from N(N-1)/2. Call this A.

从N(N-1)/2中减去所有数字的和。称之为一个。

Subtract the sum of the squares from N(N-1)(2N-1)/6. Divide this by A. Call the result B.

减去N(N-1)(N-1)(2 -1)/6的平方和。除以a，结果B。

The number which was removed is (B + A)/2 and the number it was replaced with is (B - A)/2.

去掉的数字是(B + A)/2，被替换的数字是(B - A)/2。

Example:

The vector is [0, 1, 1, 2, 3, 5]:

向量是[0,1,1,2,3,5]:

• N = 6

  N = 6

• Sum of the vector is 0 + 1 + 1 + 2 + 3 + 5 = 12. N(N-1)/2 is 15. A = 3.

  向量的和是0 + 1 + 1 + 2 + 3 + 5 = 12。N(N - 1)/ 2 = 15。= 3。

• Sum of the squares is 0 + 1 + 1 + 4 + 9 + 25 = 40. N(N-1)(2N-1)/6 is 55. B = (55 - 40)/A = 5.

  平方和是0 + 1 + 1 + 4 + 9 + 25 = 40。N(N - 1)(2 N - 1)/ 6 = 55。B = (55 - 40)/A = 5。

• The number which was removed is (5 + 3) / 2 = 4.

  去掉的数是(5 + 3)/ 2 = 4。

• The number it was replaced by is (5 - 3) / 2 = 1.

  被替换的数字是(5 - 3)/ 2 = 1。

Why it works:

• The sum of the original vector [0, ..., N-1] is N(N-1)/2. Suppose the value a was removed and replaced by b. Now the sum of the modified vector will be N(N-1)/2 + b - a. If we subtract the sum of the modified vector from N(N-1)/2 we get a - b. So A = a - b.

  原始向量的和[0，…,N - 1)N(N - 1)/ 2。假设a的值被移除并被b取代，那么修改后的向量的和将是N(N-1)/2 + b - a，如果我们从N(N-1)/2中减去修正向量的和，得到a - b，那么a = a - b。

• Similarly, the sum of the squares of the original vector is N(N-1)(2N-1)/6. The sum of the squares of the modified vector is N(N-1)(2N-1)/6 + b2 - a2. Subtracting the sum of the squares of the modified vector from the original sum gives a2 - b2, which is the same as (a+b)(a-b). So if we divide it by a - b (i.e., A), we get B = a + b.

  同样，原向量的平方和是N(N-1)(2 -1)/6。修正向量的平方和为N(N-1)(2 -1)/6 + b2 - a2。从原来的和中减去修改后的向量的平方和，得到a2 - b2，与(a+b)(a-b)相同。所以如果我们除以a - b(即。我们得到B = A + B。

• Now B + A = a + b + a - b = 2a and B - A = a + b - (a - b) = 2b.

  现在B + A = A + B + A - B = 2a, B - A = A + B - (A - B) = 2b。

#3

You can do it in O(N) time without any extra space. Here is how the algorithm works :

你可以在O(N)时间内完成，而不需要额外的空间。下面是算法的工作原理:

Iterate through array in the following manner :

以下列方式遍历数组:

1. For each element encountered, set its corresponding index value to negative. Eg : if you find a[0] = 2. Got to a[2] and negate the value.

   对于所遇到的每个元素，将相应的索引值设置为负数。如果你找到一个[0]= 2。得到a[2]并否定其值。

   By doing this you flag it to be encountered. Since you know you cannot have negative numbers, you also know that you are the one who negated it.

   通过这样做，您可以标记将要遇到的内容。因为你知道你不能有负数，你也知道你是否定它的人。

2. Check if index corresponding to the value is already flagged negative, if yes you get the duplicated element. Eg : if a[0]=2 , go to a[2] and check if it is negative.

   检查与该值对应的索引是否已经被标记为负数，如果是，您将得到复制的元素。如果a[0]=2，转到a[2]，检查它是否为负。

Lets say you have following array :

假设你有以下数组:

int a[]  = {2,1,2,3,4};

After first element your array will be :

在第一个元素之后，你的数组将是:

int a[] = {2,1,-2,3,4};

After second element your array will be :

在第二个元素之后，你的数组将是:

int a[] = {2,-1,-2,3,4};

When you reach third element you go to a[2] and see its already negative. You get the duplicate.

当你到达第三个元素时，你进入[2]，看到它已经是负的。你得到了复制。

#4

Scan the array 3 times:

扫描阵列3次:

1. XOR together all the array elements -> A. XOR together all the numbers from 0 to N-1 -> B. Now A XOR B = X XOR D, where X is the removed element, and D is the duplicate element.
2. XOR将所有数组元素-> A. XOR组合在一起，所有的数字从0到N-1 ->。现在A XOR B = XOR D，其中X是被删除的元素，D是复制元素。
3. Choose any non-zero bit in A XOR B. XOR together all the array elements where this bit is set -> A1. XOR together all the numbers from 0 to N-1 where this bit is set -> B1. Now either A1 XOR B1 = X or A1 XOR B1 = D.
4. 在XOR B. XOR中选择任意一个非零的位，将这个位的所有数组元素集合在一起——> A1。XOR把所有的数字从0到N-1都设为> B1。现在是A1 XOR B1 = X或A1 XOR B1 = D。
5. Scan the array once more and try to find A1 XOR B1. If it is found, this is the duplicate element. If not, the duplicate element is A XOR B XOR A1 XOR B1.
6. 再次扫描数组，尝试找到A1 XOR B1。如果找到了，这就是重复元素。如果没有，重复的元素是XOR B XOR A1 XOR B1。

#5

I suggest using a BitSet. We know N is small enough for array indexing, so the BitSet will be of reasonable size.

我建议使用一个位集。我们知道N足够小，可以进行数组索引，因此位集的大小是合理的。

For each element of the array, check the bit corresponding to its value. If it is already set, that is the duplicate. If not, set the bit.

对于数组中的每个元素，检查对应于其值的位。如果已经设置好了，那就是复制。如果没有，设置这个位。

#6

Use a HashSet to hold all numbers already seen. It operates in (amortized) O(1) time, so the total is O(N).

使用一个HashSet来保存已经看到的所有数字。它的作用是(平摊)O(1)时间，所以总的是O(N)。

#7

Use hashtable. Including an element in a hashtable is O(1).

使用哈希表。包括hashtable中的元素O(1)。

#8

One working solution:

一个工作的解决方案:

asume number are integers

asume数是整数

create an array of [0 .. N]

创建一个数组[0 ..N]

int[] counter = new int[N];

Then iterate read and increment the counter:

然后迭代读取和增加计数器:

 if (counter[val] >0) {
   // duplicate
 } else {
   counter[val]++;
 }

#9

@rici is right about the time and space usage: "This can be done in O(n) time and O(1) space."

@rici对时间和空间的使用是正确的:“这可以在O(n)时间和O(1)空间中完成。”

However, the question can be expanded to broader requirement: it's not necessary that there is only one duplicate number, and numbers might not be consecutive.

但是，问题可以扩展到更广泛的需求:没有必要只有一个重复的数字，而且数字可能不是连续的。

OJ puts it this way here: (note 3 apparently can be narrowed)

OJ这样说:(显然，3可以缩小)

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

给定一个包含n + 1整数的数组nums，每个整数在1和n之间(包含)，证明至少有一个重复的数字存在。假设只有一个重复的数字，找到重复的数字。

Note:

注意:

• You must not modify the array (assume the array is read only).
• 您不能修改数组(假设数组是只读的)。
• You must use only constant, O(1) extra space.
• 你必须只使用常数，O(1)额外空间。
• Your runtime complexity should be less than O(n2).
• 您的运行时复杂性应该小于O(n2)。
• There is only one duplicate number in the array, but it could be repeated more than once.
• 数组中只有一个重复的数字，但是可以重复多次。

The question is very well explained and answered here by Keith Schwarz, using Floyd's cycle-finding algorithm:

这个问题很好地解释了，由Keith Schwarz在这里回答，使用Floyd的循环查找算法:

The main trick we need to use to solve this problem is to notice that because we have an array of n elements ranging from 0 to n - 2, we can think of the array as defining a function f from the set {0, 1, ..., n - 1} onto itself. This function is defined by f(i) = A[i]. Given this setup, a duplicated value corresponds to a pair of indices i != j such that f(i) = f(j). Our challenge, therefore, is to find this pair (i, j). Once we have it, we can easily find the duplicated value by just picking f(i) = A[i].

我们要解决这个问题的主要技巧是注意到，因为我们有一个n个元素的数组，从0到n - 2，我们可以把数组看作是定义一个函数f从集合{0,1，…，n - 1}。这个函数由f(i) = A[i]定义。给定这个设置，一个重复的值对应于一对索引i != j，这样f(i) = f(j)。因此，我们的挑战是找到这对(i, j)。一旦我们有了它，我们就可以很容易地通过选择f(i) = A[i]来找到重复的值。

But how are we to find this repeated value? It turns out that this is a well-studied problem in computer science called cycle detection. The general form of the problem is as follows. We are given a function f. Define the sequence x_i as

但是我们如何找到这个重复的价值呢?事实证明，这是一个在计算机科学中被广泛研究的问题，叫做循环检测。问题的一般形式如下。我们得到了一个函数f，定义了序列x_i。

    x_0     = k       (for some k)
    x_1     = f(x_0)
    x_2     = f(f(x_0))
    ...
    x_{n+1} = f(x_n)

Assuming that f maps from a domain into itself, this function will have one of three forms. First, if the domain is infinite, then the sequence could be infinitely long and nonrepeating. For example, the function f(n) = n + 1 on the integers has this property - no number is ever duplicated. Second, the sequence could be a closed loop, which means that there is some i so that x_0 = x_i. In this case, the sequence cycles through some fixed set of values indefinitely. Finally, the sequence could be "rho-shaped." In this case, the sequence looks something like this:

假设f从一个域映射到自身，这个函数将有三种形式之一。首先，如果域是无限的，那么序列可以无限长且不重复。例如，在整数上的函数f(n) = n + 1有这个属性——没有数字是重复的。第二，序列可以是一个闭环，也就是说有一些i，所以x_0 = x_i。在这种情况下，序列循环通过一些固定的值。最后，序列可能是“rhoshape”。在这种情况下，序列看起来是这样的:

 x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
                    ^                       |
                    |                       |
                    +-----------------------+

That is, the sequence begins with a chain of elements that enters a cycle, then cycles around indefinitely. We'll denote the first element of the cycle that is reached in the sequence the "entry" of the cycle.

也就是说，序列以进入循环的元素链开始，然后无限循环。我们将表示周期中到达的周期的第一个元素，即循环的“进入”。

An python implementation can also be found here:

在这里也可以找到python实现:

def findDuplicate(self, nums):
    # The "tortoise and hare" step.  We start at the end of the array and try
    # to find an intersection point in the cycle.
    slow = 0
    fast = 0

    # Keep advancing 'slow' by one step and 'fast' by two steps until they
    # meet inside the loop.
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]

        if slow == fast:
            break

    # Start up another pointer from the end of the array and march it forward
    # until it hits the pointer inside the array.
    finder = 0
    while True:
        slow   = nums[slow]
        finder = nums[finder]

        # If the two hit, the intersection index is the duplicate element.
        if slow == finder:
            return slow

#10

This is an alternative solution in O(n) time and O(1) space. It is similar to rici's. I find it a bit easier to understand but, in practice, it will overflow faster.

这是O(n)时间和O(1)空间的另一种解决方案。它和rici类似。我发现它更容易理解，但实际上，它会溢出更快。

Let X be the missing number and R be the repeated number.

让X是缺失的数，R是重复的数。

1. We can assume the numbers are from [1..n], i.e. zero does not appear. In fact, while looping through the array, we can test if zero was found and return immediately if not.

   我们可以假设这些数字是[1]。n]，即0不出现。实际上，在遍历数组时，我们可以测试是否找到了0，如果没有，则立即返回。

2. Now consider:

   现在考虑:

   sum(A) = n (n + 1) / 2 - X + R
   
   product(A) = n! R / X
   

where product(A) is the product of all element in A skipping the zero. We have two equations in two unknowns from which X and R can be derived algebraically.

其中product(A)是所有元素在跳过零点时的乘积。我们有两个方程，两个未知数X和R可以用代数方法推导出来。

Edit: by popular demand, here is a worked-out example:

编辑:根据大众需求，这里有一个很受欢迎的例子:

Let's set:

让我们设置:

S = sum(A) - n (n + 1) / 2
P = n! / product(A)

Then our equations become:

然后我们的方程变成:

R - X = S
X = R P

which can be solved to:

可以解决的问题是:

R = S / (1 - P)
X = P R = P S / (1 - P)

Example:

例子:

A = [0 1 2 2 4]

n = A.length - 1 = 4
S = (1 + 2 + 2 + 4) - 4 * 5 / 2 = -1
P = 4! / (1 * 2 * 2 * 4) = 3 / 2

R = -1 / (1 - 3/2) = -1 / -1/2 = 2
X = 3/2 * 2 = 3

#11

You could proceed as follows:

你可以这样做:

1. sort your array by using a Linear-time sorting algorithm (e.g. Counting sort) - O(N)
2. 使用线性时间排序算法(例如计数排序)- O(N)对数组进行排序
3. scan the sorted array and stop as soon as two consecutive elements are equal - O(N)
4. 扫描已排序的数组，并在两个连续的元素相等时停止(N)

#12

public class FindDuplicate {
    public static void main(String[] args) {
        // assume the array is sorted, otherwise first we have to sort it.
        // time efficiency is o(n)
        int elementData[] = new int[] { 1, 2, 3, 3, 4, 5, 6, 8, 8 };
        int count = 1;
        int element1;
        int element2;

        for (int i = 0; i < elementData.length - 1; i++) {
            element1 = elementData[i];
            element2 = elementData[count];
            count++;
            if (element1 == element2) {
                System.out.println(element2);
            }
        }
    }
}

#13

  public void duplicateNumberInArray {
    int a[] = new int[10];
    Scanner inp = new Scanner(System.in);
    for(int i=1;i<=5;i++){  
        System.out.println("enter no. ");
        a[i] = inp.nextInt();
    }
    Set<Integer> st = new HashSet<Integer>();
    Set<Integer> s = new HashSet<Integer>();
    for(int i=1;i<=5;i++){          
        if(!st.add(a[i])){
            s.add(a[i]);
        }
    }

    Iterator<Integer> itr = s.iterator();
                System.out.println("Duplicate numbers are");
    while(itr.hasNext()){
        System.out.println(itr.next());
    }
}

First of all creating an array of integer using Scanner class. Then iterating a loop through the numbers and checking if the number can be added to set (Numbers can be added to set only when that particular number should not be in set already, means set does not allow duplicate no. to add and return a boolean vale FALSE on adding duplicate value).If no. cannot be added means it is duplicate so add that duplicate number into another set, so that we can print later. Please note onething that we are adding the duplicate number into a set because it might be possible that duplicate number might be repeated several times, hence add it only once.At last we are printing set using Iterator.

首先，使用扫描仪类创建一个整数数组。然后遍历数字并检查数字是否可以添加到集合中(只有当这个特定的数字不应该被设置时，才可以添加数字，这意味着set不允许重复no。要添加和返回一个布尔谷值假，添加重复值)。如果没有。不能添加的意思是它是重复的，所以将复制的数字添加到另一个集合中，这样我们就可以在以后打印。请注意，我们正在将重复的数字添加到一个集合中，因为可能重复的数字可能重复多次，因此只添加一次。最后我们使用迭代器来打印set。

#14

//This is similar to the HashSet approach but uses only one data structure:

//这类似于HashSet方法，但只使用一个数据结构:

    int[] a = { 1, 4, 6, 7, 4, 6, 5, 22, 33, 44, 11, 5 };

    LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();

    for (int i : a) {
        map.put(i, map.containsKey(i) ? (map.get(i)) + 1 : 1);
    }

    Set<Entry<Integer, Integer>> es = map.entrySet();
    Iterator<Entry<Integer, Integer>> it = es.iterator();

    while (it.hasNext()) {
        Entry<Integer, Integer> e = it.next();
        if (e.getValue() > 1) {
            System.out.println("Dupe " + e.getKey());
        }
    }

#15

We can do using hashMap efficiently:

我们可以有效地使用hashMap:

Integer[] a = {1,2,3,4,0,1,5,2,1,1,1,};
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int x : a)
{
    if (map.containsKey(x))  map.put(x,map.get(x)+1);
    else map.put(x,1);
}

Integer [] keys = map.keySet().toArray(new Integer[map.size()]);
for(int x : keys)
{
    if(map.get(x)!=1)
    {
        System.out.println(x+" repeats : "+map.get(x));
    }
}

#16

This program is based on c# and if you want to do this program using another programming language you have to firstly change an array in accending order and compare the first element to the second element.If it is equal then repeated number found.Program is

这个程序是基于c#的，如果你想用另一种编程语言来做这个程序，你必须首先改变一个数组的重音顺序，并将第一个元素与第二个元素进行比较。如果它是相等的，那么重复的数字就会被发现。程序是

int[] array=new int[]{1,2,3,4,5,6,7,8,9,4};
Array.Sort(array);
for(int a=0;a<array.Length-1;a++)
{
  if(array[a]==array[a+1]
  {
     Console.WriteLine("This {0} element is repeated",array[a]);
   }
}
Console.WriteLine("Not repeated number in array");

#17

1. sort the array O(n ln n)
2. 对数组O(n ln n)进行排序

3. using the sliding window trick to traverse the array O(n)

   使用滑动窗口技巧遍历数组O(n)

   Space is O(1)

   空间是O(1)

   Arrays.sort(input);
   for(int i = 0, j = 1; j < input.length ; j++, i++){
       if( input[i] == input[j]){
           System.out.println(input[i]);
           while(j < input.length && input[i] == input[j]) j++;
           i = j - 1;
       }
   }
   

Test case int[] { 1, 2, 3, 7, 7, 8, 3, 5, 7, 1, 2, 7 }

测试用例int[]{1、2、3、7、7、8、3、5、7、1、2、7}

output 1, 2, 3, 7

输出1 2 3 7。

#18

Traverse through the array and check the sign of array[abs(array[i])], if positive make it as negative and if it is negative then print it, as follows:

遍历数组并检查数组[abs(i])的符号，如果正的使其为负，如果为负，则将其打印出来，如下所示:

import static java.lang.Math.abs;

public class FindRepeatedNumber {

    private static void findRepeatedNumber(int arr[]) {
        int i;
        for (i = 0; i < arr.length; i++) {
            if (arr[abs(arr[i])] > 0)
                arr[abs(arr[i])] = -arr[abs(arr[i])];
            else {
                System.out.print(abs(arr[i]) + ",");
            }
        }
    }

    public static void main(String[] args) {
        int arr[] = { 4, 2, 4, 5, 2, 3, 1 };
        findRepeatedNumber(arr);
    }
}

Reference: http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/

参考:http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/

#19

As described,

所述,

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.

你有一个从0到n-1的数组，其中一个数字被删除了，然后用一个已经在数组中的数字替换，这个数字复制了这个数字。

I'm assuming elements in the array are sorted except the duplicate entry. If this is the scenario , we can achieve the goal easily as below :

我假设数组中的元素都是有序的除了重复输入。如果是这样，我们可以很容易地达到目标:

        public static void main(String[] args) {
    //int arr[] = { 0, 1, 2, 2, 3 };
    int arr[] = { 1, 2, 3, 4, 3, 6 };
    int len = arr.length;
    int iMax = arr[0];
    for (int i = 1; i < len; i++) {
        iMax = Math.max(iMax, arr[i]);
        if (arr[i] < iMax) {
            System.out.println(arr[i]);
            break;
        }else if(arr[i+1] <= iMax) {
            System.out.println(arr[i+1]);
            break;
        }
    }
}

• O(n) time and O(1) space ;please share your thoughts.
• O(n)时间和O(1)空间;请分享你的想法。

#20

int a[] = {2,1,2,3,4};

int b[] = {0};

for(int i = 0; i < a.size; i++)
{

    if(a[i] == a[i+1])
    {
         //duplicate found
         //copy it to second array
        b[i] = a[i];
    }
}