数组中是否有重复的数字？

Question

有大小为 n 的数组。这些值可以作为索引介于 0 和 (n-1) 之间。

例如：array[4] = {0, 2, 1, 3}

我应该说有没有重复超过1次的数字

例如：array[5] = {3,4,1,2,4} -> return true因为4重复了。

这个问题有很多不同的解决方案，我想知道这个具体的解决方案是否合适（如果是，请证明，否则反驳）。

我的解决方案（让我们看下一个例子）：

array: indices   0   1   2   3   4
       values    3   4   1   2   0

所以我建议：

计算索引的总和 (4x5 / 2 = 10) 并检查值的总和 (3+4+1+2+0) 是否等于该总和。如果没有，则有重复的数字。
除第一个条件外，获取索引的乘积（0 除外，因此：1x2x3x4）并检查它是否等于值的乘积（0 除外，因此：3x4x1x2x0）。

=> 如果在每个条件下都相等，那么我说没有重复的数字。否则，有一个重复的数字。

是否正确？如果是，请证明它或给我看一个link。否则请反驳

Answer 1

如果要在数组中搜索重复项，有一个简单的方法：

int N =5;
int array[N] = {1,2,3,4,4};

for (int i = 0; i< N; i++){
    for (int j =i+1; j<N; j++){
        if(array[j]==array[i]){
            std::cout<<"DUPLICATE FOUND\n";
            return true;
        }
    }
}
return false;

查找重复项的其他简单方法是使用 std::set 容器，例如：

std::set<int> set_int;
set_int.insert(5);
set_int.insert(5);
set_int.insert(4);
set_int.insert(4);
set_int.insert(5);
std::cout<<"\nsize "<<set_int.size();

输出将为 2，因为有 2 个单独的值

Answer 2

为什么你的算法是错误的？

你的解决方案是错误的，这里有一个反例（可能有更简单的，但我很快就找到了这个）：

int arr[13] = {1, 1, 2, 3, 4, 10, 6, 7, 8, 9, 10, 11, 6};

总和为78，乘积为479001600，如果取大小为13的普通数组：

int arr[13] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};

它还有 78 的总和和 479001600 的乘积，所以你的算法不起作用。

如何找到反例？¹

求反例^{2 3}:

取一个从0到N - 1的数组；
在0和N - 1之间挑两个偶数³M1 > 2和M2 > 2对分；
将 P1 = M1/2 - 1 替换为 2 * P1，将 P2 = M2/2 + 1 替换为 2 * P2。

在原始数组中你有：

 Product = M1 * P1 * M2 * P2

 Sum = 0 + M1 + P1 + M2 + P2
     = M1 + M1/2 - 1 + M2 + M2/2 + 1
     = 3/2 * (M1 + M2)

在新数组中你有：

Product = M1/2 * 2 * P1 + M2/2 * 2 * P2
        = M1 * P1 * M2 * P2

Sum = M1/2 + 2P1 + M2/2 + 2P2
    = M1/2 + 2(M1/2 - 1) + M2/2 + 2(M2/2 + 1)
    = 3/2 * M1 - 2 + 3/2 * M2 + 2
    = 3/2 * (M1 + M2)

所以两个数组的总和和乘积都相同，但是其中一个数组有重复的值，所以你的算法不起作用。

_{¹ 这是一种查找反例的方法，可能还有其他方法（有可能还有其他方法） .}

_{² 这与我用来查找第一个计数器示例的方法不完全相同 - 在原始方法中，我只使用了一个数字 M 并使用了这样一个事实，即您可以在不更改产品的情况下将 0 替换为 1，但我在这里提出了一种更通用的方法，以避免出现诸如 [=124 之类的争论=].}

_{³ 该方法不适用于小数组，因为您需要找到 2 个偶数 M1 > 2 和 M2 > 2 这样M1/2 != M2（并且相互）和 M1/2 - 1 != M2/2 + 1，这（我认为）对于任何大小小于 14 的数组都是不可能的。}

哪些算法有效？⁴

算法 1：O(n) 时间和 space 复杂度。

如果您可以分配一个大小为 N 的新数组，那么：

template <std::size_t N>
bool has_repetition (std::array<int, N> const& array) {
    std::array<bool, N> rep = {0};
    for (auto v: array) {
        if (rep[v]) {
            return true;
        }
        rep[v] = true;
    }
    return false;
}

算法2：O(nlog(n))时间复杂度和O(1)space复杂度，可变数组。

您可以简单地对数组进行排序：

template <std::size_t N>
bool has_repetition (std::array<int, N> &array) {
    std::sort(std::begin(array), std::end(array));
    auto it = std::begin(array);
    auto ne = std::next(it);
    while (ne != std::end(array)) {
        if (*ne == *it) {
            return true;
        }
        ++it; ++ne;
    }
    return false;
}

算法 3: O(n^2) 时间复杂度和 O(1) space 复杂度，具有非可变数组。

template <std::size_t N>
bool has_repetition (std::array<int, N> const& array) {
    for (auto it = std::begin(array); it != std::end(array); ++it) {
        for (auto jt = std::next(it); jt != std::end(array); ++jt) {
            if (*it == *jt) {
                return true;
            }
        }
    }
    return false;
}

_{⁴ 这些算法确实有效，但可能存在其他性能更好的算法 - 这些只是我能想到的最简单的算法 "restrictions".}

Answer 3

你的方法有什么问题吗？

您的方法计算数据的一些统计数据并将它们与预期的排列（= 正确答案）进行比较。虽然违反这些比较中的任何一个都是决定性的（数据不能满足约束），但反之则不一定如此。您只查看两个统计数据，对于足够大的数据集来说，这些统计数据太少了。由于数据是整数，你的方法可能失败的最小数据数大于3。

Answer 4

更深入的解释为什么你的算法是错误的：

count the sum of the indices (4x5 / 2 = 10) and check that the values' sum (3+4+1+2+0) is equal to this sum. if not, there's repeated number.

给定任何没有重复项的数组 A，很容易创建满足您的第一个要求但现在包含重复项的数组。只需取两个值，然后将其中一个值减去某个值 v，然后将该值加到另一个值上。或者采用多个值并确保它们的总和保持不变。（只要新值仍在 0 .. N-1 范围内。）对于 N = 3，已经可以将 {0,1,2} 更改为 {1,1,1}。对于大小为 3 的数组，有 7 个组合具有正确的总和，但 1 个是误报。对于大小为 4 的数组，44 个中有 20 个重复，对于大小为 5 的数组，有 381 个中有 261 个重复，对于大小为 6 的数组，有 4332 个中有 3612 个，依此类推。可以肯定的是，误报数量的增长 比真正的多 快得多。

in addition to the first condition, get the multiplication of the indices(except 0. so: 1x2x3x4) and check if it's equal to the values' multiplication (except 0, so: 3x4x1x2x0).

第二个要求涉及所有大于 0 的索引的乘法。很容易意识到这也不是一个非常强的限制。一旦其中一个指数不是素数，所有指数的乘积就不再与被乘数唯一相关，并且可以用不同的值构造一个列表，结果相同。例如。一对2和6可以用3和4代替，2和9可以用6和3代替，依此类推。显然，随着数组大小变大和更多的非素数被用作被乘数，误报的数量增加。

None这几个要求真是强得无法弥补。由于第二个限制甚至不考虑 0，因此对于从大小 5 开始的数组，可以相当容易地创建误报。任何一对 0 和 4 都可以简单地用任何唯一数组中的两个 2 替换，例如 {2, 1, 2, 3, 2}

您需要的是与出现的值非常紧密的结果。您可以将第二个要求调整为更复杂的方法并跳过非主要值并考虑 0 。例如，您可以使用第一个素数作为 0 的被乘数 (2)，使用 3 作为 1 的被乘数，5 作为 2 的被乘数，等等。那会起作用（您不需要第一个要求），但这种方法会过于复杂。获得唯一结果的更简单方法是 OR 每个值的第 i 位 (0 => 1 << 0, 1 => 1 << 1, 2 => 1 << 2，依此类推。（显然，检查某个位是否已被重复值设置比等待最终结果更快。这在概念上与使用 bool array/vector 来自另一个例子！）

数组中是否有重复的数字？

Is there any number repeated in the array?

c++

arrays

numbers

repeat

为什么你的算法是错误的？

如何找到反例？¹

哪些算法有效？⁴

数组中是否有重复的数字？

Is there any number repeated in the array?

c++

arrays

numbers

repeat

为什么你的算法是错误的？

如何找到反例？1

哪些算法有效？4

如何找到反例？¹

哪些算法有效？⁴