在数组中查找重复项 [英] Find duplicate in an array

问题描述

给出一个由n + 1个介于1和n之间的整数组成的只读数组，找到一个数字，该数字在小于O(n)的空间内以线性时间重复，并依次遍历流O(1)次.

Sample Input: [3 4 1 4 1]
Sample Output : 1/4(any one of these)

如果有多个可能的答案(例如上述示例)，则输出任意一个.

如果没有重复，则输出-1.

我尝试过以下解决方案:

int Solution::repeatedNumber(const vector<int> &A) {

    vector<bool> v(A.size(), true);

    for (int i = 0; i < A.size(); i++) {
        if (v[A[i]])
            v[A[i]] = false;
        else
            return A[i];
    }
}

这已经被接受了，但是它在内存中比O(n)小吗?

解决方案

您在想知道为什么会接受这是正确的.这个答案显然是O(n)空间复杂性.您分配一些与n成正比的数据量，使其成为O(n)空间.无论判断您的程序是错误地接受它.法官可能会接受您的分数，因为您使用的字节数少于A分配的字节数，但这只是推测.

下面的代码实际上不是该问题的解决方案.上面的方法是对一个更简单问题的解决方案.下面的解决方案忽略了流必须是只读的约束.经过一些研究，看来该问题是类型为"em"的一系列类似问题的一个非常困难的版本，给出一个介于1和n之间的数字范围，找到重复/缺失的数字". .如果仅重复一个数字，并且只需要O(n)时间，则可以使用上述布尔向量.如果仅重复一个数字，但是您限于固定的空间，则可以实现此怪兽.

以下是在其限制范围内解决此问题的方法:

您可以执行以下操作:

#include<vector>
#include<iostream>
int repeating(std::vector<int>& arr)
{
  for (int i = 0; i < arr.size(); i++)
  {
    if (arr[abs(arr[i])] >= 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else {
      return abs(arr[i]);
    }
  }
}
int main()
{
        std::vector<int> v{1,2,3,4,5,1};

        std::cout<<repeating(v)<<std::endl;
        std::cout<<sizeof(v)*sizeof(v[0])<<std::endl;
        return 0;
}

上面的程序使用输入数组本身来跟踪重复项.对于每个索引i，该数组评估arr [i].该数组将arr(arr [i])设置为负.取反值是一个容易逆的操作(只需取元素的绝对值)，因此可以在不破坏数据完整性的情况下将其用于标记数组的索引.如果遇到索引使arr [abs(arr [i])]为负，则您知道在数组中之前已经看到过abs(arr [i])).这使用O(1)空间复杂度，遍历数组一次，可以修改以返回任何或所有重复的数字.

Given a read only array of n + 1 integers between 1 and n, find one number that repeats in linear time using less than O(n) space and traversing the stream sequentially O(1) times.

Sample Input: [3 4 1 4 1]
Sample Output : 1/4(any one of these)

If there are multiple possible answers (like in the sample case above), output any one.

If there is no duplicate, output -1.

I tried doing a solution of this which is:

int Solution::repeatedNumber(const vector<int> &A) {

    vector<bool> v(A.size(), true);

    for (int i = 0; i < A.size(); i++) {
        if (v[A[i]])
            v[A[i]] = false;
        else
            return A[i];
    }
}

This is getting accepted but how is this less than O(n) in memory?

解决方案

You are correct in wondering why this would be accepted. This answer is obvious O(n) space complexity. You allocating some amount of data that grows directly proportionally with n, making it O(n) space. Whatever is judging your program is incorrectly accepting it. It may be possible that the judge is accepting your score because you are using less bytes than are allocated by A, but that is only speculation.

EDIT: The code bellow isn't actually a solution to the problem. It is a solution to a simpler problem along the lines of the above. The solution below ignores the constraint that the stream must be read only. After doing some research, it appears that this problem is a very difficult version of a series of similar problems of the type "Given a range of numbers between 1 and n, find the repeating/missing number". If there were only one number repeated, and there was only a O(n) time requirement, you could use a bool vector as above. If there were only one number repeated, but you were constrained to constant space, you could implement this solution where we use gauss's formula to find the sum of integers from 1 to n, and subtract that from the sum of the array. If the array had two missing numbers, and you were constrained to constant time, you could implement this solution where we use the sum and product of the array to create a system of equations which can be solved in O(n) time with O(1) space.

To solve the question posed above, it looks like one would have to implement something to the order of this monstrosity.

Here is a solution this problem within its constraints:

You could do something like this:

#include<vector>
#include<iostream>
int repeating(std::vector<int>& arr)
{
  for (int i = 0; i < arr.size(); i++)
  {
    if (arr[abs(arr[i])] >= 0)
      arr[abs(arr[i])] = -arr[abs(arr[i])];
    else {
      return abs(arr[i]);
    }
  }
}
int main()
{
        std::vector<int> v{1,2,3,4,5,1};

        std::cout<<repeating(v)<<std::endl;
        std::cout<<sizeof(v)*sizeof(v[0])<<std::endl;
        return 0;
}

The above program uses the input array itself to track duplicates. For each index i, the array evaluates arr[i]. The array sets arr(arr[i]) negative. Negating a value is an easily reversible operation (simply take the absolute value of the element), so it can be used to mark an index of the array without ruining the integrity of the data. If you ever encounter an index such that arr[abs(arr[i])] is negative, you know that you have seen abs(arr[i])) before in the array. This uses O(1) space complexity, traverses the array once, and can be modified to return any or all duplicate numbers.

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