在数组中查找重复项

Question

在数组中查找重复项

3

给定一个只读的数组，包含n + 1个整数，这些整数的取值范围在1到n之间。请在线性时间内找出其中重复的一个数，并且使用少于O(n)的空间，在顺序遍历流时仅遍历一次。

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)更节省内存？

- Kaustubh Mundra

这个解决方案使用了O(n)的额外空间。它不少于O(n)。 - François Andrieux

你可以使用 bool 而非 int，因此可能只是检查内存使用是否小于 n*sizeof(int)？我不确定，因为看起来你是对的，内存增长速度将会是 n。 - Carl Shiles

@Rabbid76 我不知道 std::set 是否有任何大小保证，但它的大小至少与其元素的总和一样大。如果您需要存储最多 n 个元素，则您的内存需求至少为 O(n)。 - François Andrieux

1

@Rabbid76 O(n)和O(n-1)是相同的复杂度。而O(n)是一个下限，std::set可能会占用更多的内存，据我所知标准没有提供任何保证。 - François Andrieux

1

顺便说一下，虽然似乎每个人都已经知道了，但返回值永远不可能是“-1”，因为从整数“1”到“n”的输入有“n+1”个，这就是所谓的鸽笼原理。 - nglee

6个回答

3

std::vector<bool> 是一个位集，因此它将使用 n 个比特。按照大O记号， O(n/8)=O(n)，这意味着空间不少于 O(n)。

我认为他们没有看实际程序，而只是在一些示例运行中测量其空间消耗。因此，使用位向量技巧使其误以为自己比 O(n) 更好。

但我同意你的观点。这不应该被接受。

- Philipp Claßen

1

我有一个解决方案，需要O(sqrt(N))的空间和O(N)的时间，并且遍历列表两次--假设能够在O(1)的时间内计算整数平方根（对于任意大的N，这可能至少是O(log(N))操作）。

首先分配一个大小为ceil(sqrt(N))的整数数组A1，用0填充。
遍历数组，对于每个元素x：
- 计算k=floor(sqrt(x))
- 增加A1[k]
- 如果A1[k]>2k+1，则k²和(k+1)²-1之间必须至少有一个重复项。(对于k=floor(sqrt(N))，阈值是N-k²。记住k并且中断第一次迭代
可选地删除第一个数组
分配一个大小为2k+1的布尔数组A2，用false填充。
再次遍历所有x：
- 检查是否设置了A2[x-k²]，如果是，则x是重复的
- 否则，增加A2[x-k²]

该解决方案还适用于更大和更小的数组（不需要完全是N+1），如果没有重复项，则第一次迭代将运行到结束。两个临时数组都是O(k)（如果您很严谨，第一个数组是O(k*log(k))，因为它必须存储大小为sqrt(N)的整数）。

- chtz

1

因为你提供了一个解决问题的方案，而且还尽可能地减少了对原始方法的修改，所以我给你点赞。如果想要一个高级的O(1)附加内存解决方案，同时不修改输入，请参考在循环入口处查找重复项。 - greybeard

0

std::vector<bool> 不同于其他任何向量。

std::vector<bool> 是 std::vector 的一种可能节省空间的特化类型，用于存储布尔值。

这就是为什么它可能使用更少的内存，因为它可以用一个字节表示多个布尔值，就像位集一样。

- RDP

0

在上面的答案中，@jayson Boubin建议的解决方案是O(1)-space方法，它非常好（顺便说一下，它真的很棒！），当允许更改原始数组或更改不重要时。但是，如果不允许更改原始数组，则众所周知的解决方案是O(sqrt(n))-space和O(n)-time，该方法基本上建议我们首先考虑sqrt(n)-ranges，其中第i个范围将是[sqrt(n)*i 到 sqrt(n)*(i+1)]，然后我们遍历数组并计算每个范围内的元素数等等...

看一下：leetcode: 寻找重复数字

- Ajay jangid

-1

由于您只是在原地进行比较，而不创建新的数据结构来存储任何内容或进行任何比较，因此它在内存中是常量（O（1））。

您还可以使用哈希表，例如unordered_set，但这将使用O（N）内存 - 但仍保持O（N）时间复杂度。

顺便说一句，我不确定这是否是“接受”的解决方案（您发布的内容是创建大小为（sizeofA）的向量），但只是根据您的需求提供了一个解决方案。

- Travis

3

那么 vector <bool> v(A.size(),true); 是什么呢？它不会创建新的数据结构来容纳任何东西或进行任何比较。 - NathanOliver

1

@Travis 不是最好的开端，相信我。 - iehrlich

首先，不需要进行人身攻击。其次，这个语句“因为你只是在原地进行比较，而没有创建新的数据结构来存储任何内容或进行任何比较，所以它在内存中是常量（O（1））。”是错误的。OP确实创建了一个额外的数据结构。 - NathanOliver

好的，我之前的理解是它必须严格小于O(N)，而不是至少。编辑：另外，我不确定原帖是否发布了。虽然我现在不确定为什么要解释两次。我误解了原帖... - Travis

@Travis 确保不要混淆 OP 提供的解决方案的要求和 OP 所提供的问题的要求。OP 尝试解决的问题需要小于 O(n) 的复杂度。他发布的解决方案具有 O(n) 的复杂度，这本不应该被接受，但却被接受了。他想知道为什么会被接受。 - François Andrieux

显示剩余2条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jayson Boubin · Accepted Answer

你想知道为什么这个答案会被接受是正确的。这个答案明显具有O(n)空间复杂度。你分配了一些数据，它与n成正比增长，使得它的空间复杂度为O(n)。无论是什么评判你的程序都是错误地接受它。可能评判者之所以接受你的分数是因为你使用的字节数少于A分配的字节数，但这只是猜测。

编辑：下面的代码实际上不是解决问题的方法。这是一个类似于上述问题的简单问题的解决方案。下面的解决方案忽略了必须只读取流的约束条件。经过一些研究，发现这个问题是一系列类似问题的非常困难的版本，类型为“在1到n之间给定一系列数字，找到重复/缺失的数字”。如果只有一个数字重复，并且只需要O(n)的时间，可以使用如上所述的bool向量。如果只有一个数字重复，但受到常数空间的限制，可以实现这个solution，其中我们使用高斯公式来找到从1到n的整数之和，并将其从数组的总和中减去。如果数组有两个缺失的数字，并且你受到常数时间的限制，你可以实现这个solution，其中我们使用数组的和与积创建一个方程组，可以在O(n)时间内用O(1)空间解决。

要解决上述提出的问题，看起来需要实现类似于这个monstrosity的东西。

这里有一个在其限制内解决此问题的方法：

你可以像这样做：

#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)空间复杂度，遍历一次数组，并且可以修改以返回任何或所有重复数字。