Существует массив из n чисел.Одно число повторяется n / 2 раза, а другие n / 2 числа различны

Question

Существует массив из n чисел.Одно число повторяется n / 2 раза, а другие n / 2 числа различны. Найдите повторное число.(Лучшее решение - это o (n) точно n / 2 + 1 сравнений.)

главная проблема здесь - n / 2 + 1 сравнений.у меня есть два решения для O (n), но они берут больше n / 2 + 1 сравнений.

1> делят числа массива на группы по три. сравните эти n / 3 группы для любых одинаковых элементов,например, массив равен (1 10 3) (4 8 1) (1 1) .... таким образом, требуемое количество сравнений равно 7, что> n / 2 + 1, т.е. 8/2 + 1 = 5

2> сравнить [i] с [i + 1] и [i + 2], например, массив равен 8 10 3 4 1 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

Прочитайте часть о сложности 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";
    }
}

Answer 3

Вам просто нужно найти число, которое существует дважды в массиве.

Вы просто начинаете с самого начала, сохраняете хэш или что-то из чисел, которые вы уже видели, когда вы попадаете на число, которое появляется дважды, просто остановитесь.

сценарий наихудшего кота: сначала вы видите все n / 2 различных числа, а затем следующее число повторяется .... n / 2 + 2 (потому что номер, который вы ищете не входит в число уникальных чисел n / 2)

Answer 4

Что касается сложности O (n / 2 + 1) и сложности пространства O (1), вы можете (почти) удовлетворить требования с помощью этого подхода:

Сравнить кортежи:

a [x] == a [x + 1], a [x + 2] == a [x + 3] ... a [n-1] == a [n]

Если нетнайдено совпадение с шагом увеличения:

a [x] == a [x + 2], a [x + 1] == a [x + 3]

Это будетв худшем случае запускайте в O (n / 2 + 2) (но всегда в O (1) пространстве), когда у вас есть такой массив: [8 1 10 1 3 1 4 1]

Answer 5

Другое решение для O (n) (но не точно n / 2 + 1), но с пробелом O (1):

Поскольку у вас n / 2 этого числа, то, если вы посмотрите на него как на отсортированный массив, есть сценарии для его положения:

Либо это наименьшее число, поэтому оно займет позиции 1-n / 2 .. или это не так, и тогда оно точно будет в позиции n / 2 + 1.

Таким образом, вы можете использовать алгоритм выбора и получить 4 элемента: диапазон [(n / 2-1), (n / 2 + 1)] в размере
Мы хотим получить число k, так что с алгоритмом все в порядке.

Тогда повторное число должно быть как минимум дважды в этих 4 числах (простая проверка)

Итак, общая сложность: 4 * O (n) + O (1) = O (n)

Answer 6

qsort( ) массив, затем сканирование для первого повтора.

Answer 7

Из-за принципа Pigeon hole вам нужно протестировать только первые n / 2 + 1 членов массива, поскольку повторное число наверняка будет повторяться как минимум дважды.Проходите по каждому элементу, используя хеш-таблицу для отслеживания, и останавливайтесь, когда есть элемент, который повторяется дважды.