Сравните каждый элемент 2D-массива с остальным C ++

Question

Я новичок в C ++, и мне нужно написать метод, который проверяет, содержит ли двумерный массив дублирующиеся элементы.

Так, например, у меня есть matrix[3][4], яудалось сравнить первый элемент [0][0] с остальными до последнего [2][3].Проблема в том, что я не знаю, как поступить, что я должен сделать, так это то, что метод затем сравнивает элемент [0][1] с остальным (за исключением предыдущего и, конечно, самого себя) и т. Д.

Answer 1

Прежде всего, тот факт, что это двумерный массив, не имеет значения в этом контексте; вы хотите найти дубликаты по всему массиву, так что в любом случае вам лучше использовать одномерную индексацию. По совпадению, это предложенный способ обработки двумерных массивов в C ++.

Итак, если вы можете расположить индексы в некотором порядке, общая идея состоит в проверке каждого элемента со всеми последующими элементами. Это даст вам O (n ² ) . Неудивительно, что псевдокод представляет собой две петли и является общей схемой, используемой, например, для обнаружения столкновений:

for (iterA = 0; iterA < num - 1; iterA++) {
    for (iterB = iterA + 1; iterB < num; iterB++) { // note how iterB starts one further
        if (*iterA == *iterB)
            return true; // found a duplicate
    }
}

В случае двумерного массива разыменование *iterA может быть заменено функцией, которая разбивает составной одномерный индекс на две составляющие, например, с i % width, i / width. Это, опять же, очень распространенный паттерн.

Как говорится, зачем? Сделайте std::set, начните помещать элементы один за другим и вызывайте find перед каждой вставкой. Если find что-то возвращает, сломайте.