有一个n个数字的数组。一个数字重复n/2次，其他n/2个数字是不同的

Question

有一个n个数字的数组。一个数字被重复n/2次，而其他n/2个数字被distinct.Find该重复的数字。(最佳解决方案是o(n)恰好n/2+1个比较。)

这里的主要问题是n/2+1比较。我有两个关于O(n)的解决方案，但它们进行了超过n/2+1的比较。

对于任何相同的元素，1>将数组的数量分成n/3组，每组n/3个three.compare。例如数组为(1 10 3) (4 8 1) (1 1)....so所需比较次数为7，大于n/2+1，即8/2+1=5

将ai与ai+1和ai+2进行比较，例如2> is 8 10 3 4 1 1 1

总共9个比较

我很感激你能帮我一点忙。谢谢

空间复杂度为O(1)。

Answer 1

当然，如果所有其他对都是不同的，则只需比较所有对。如果你找到一对两个相等的数字，你就有了这个数字

假设你有这样的数字(它只是关于索引)

[1,2,3,4,5,6,7,8,9,10]

然后进行n/2 +1比较，如下所示

(1,2),(3,4),(5,6),(7,8),(9,7),(9,8)

如果所有对都是不同的，则返回10。

重点是当你比较最后4个剩余的数字(7,8,9,10)时，你知道其中至少有两个相同的数字，你有3个比较。

Answer 2

你只需要找到在数组中存在两次的数字。

你只需要从头开始，保存一个散列或一些你已经看到的数字，当你得到一个出现两次的数字时，就停止。

最糟糕的情况:您首先看到所有n/2个不同的数字，然后下一个数字是重复的…… n/2 +2 (因为您要查找的数字不是n/2个唯一数字的一部分)

Answer 3

阅读关于O(1)空间复杂性的部分为时已晚，但不管怎样，这是我的解决方案：

#include <iterator>
#include <unordered_set>

template <typename ForwardIterator>
ForwardIterator find_repeated_element(ForwardIterator begin, ForwardIterator end)
{
    typedef typename std::iterator_traits<ForwardIterator>::value_type value_type;
    std::unordered_set<value_type> visited_elements;
    for (; begin != end; ++begin)
    {
        bool could_insert = visited_elements.insert(*begin).second;
        if (!could_insert) return begin;
    }
    return end;
}

#include <iostream>

int main()
{
    int test[] = {8, 10, 3, 4, 1, 1, 1, 1};
    int* end = test + sizeof test / sizeof *test;
    int* p = find_repeated_element(test, end);
    if (p == end)
    {
        std::cout << "the was no repeated element\n";
    }
    else
    {
        std::cout << "repeated element: " << *p << "\n";
    }
}