Поиск индексов одинаковых элементов

@Smipe · Регистрация: 13.10.2020

Студворк — интернет-сервис помощи студентам

Напишите псевдокод алгоритма, который находит в массиве два одинаковых элемента, расстояние между которыми в массиве минимально. То есть нужно найти индексы i*, j* такие, что:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?i^*, j^* = argmin\{j - i | a_i = a_j, i < j\}$
Покажите, какую вычислительную сложность имеет ваш алгоритм и почему. Считайте, что размер массива не более 10^7, а элементы массива - целые числа от -10^18 до 10^18.

Первое решение, что пришло в голову это перебрать каждый элемент за O(n^2) и запомнить индексы одинаковых элементов и их разницу и так искать минимальное расстояние. Второе решение, это отсортировать a_i по возрастанию и дальше сравнивать по 2 числа
Например:
list index: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
list value: [2, 7, 1, 2, 4, 2, 9, 10, 7, 2, 4, 4, 10, 1, 8, 2, 5, 9, 6]
Сортируем и получаем такое
list index: [2, 13, 0, 3, 5, 9, 15, 4, 10, 11, 16, 18, 1, 8, 14, 6, 17, 7, 12]
list value: [1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 5, 6, 7, 7, 8, 9, 9, 10, 10]
Сравниваем по 2 элемента и запоминаем разницу индексов, потом находим минимальное значение
Сложность O(n log n). Как решить эту задачу за O(n)?

@vantfiles · 25.07.2021, 13:27

На первом проходе складываем числа в список:

Code
1
2
3
4
5
6
7
8
9
10
11
12
list index: [00, 01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15, 16, 17, 18]
list value: [ 2,  7,  1,  2,  4,  2,  9, 10,  7,  2,  4,  4, 10,  1,  8,  2,  5,  9,  6]
 
list = {
  [ 2] = { 00, 03, 05, 09, 15, },
  [ 7] = { 01, 08, },
  [ 1] = { 02, 13, },
  [ 4] = { 04, 10, 11, },
  [ 9] = { 06, 17, },
  [10] = { 07, 12, },
  [ 8] = { 14, },
}

На втором ищем минимальную разницу.

@Puporev · 25.07.2021, 13:28

Сообщение от Smipe

Второе решение, это отсортировать a_i

Так индексы изменятся.

@vantfiles · 25.07.2021, 13:30

Да, как только найдется пара с разницей в 1, дальше можно не крутить - все равно меньше не будет.

@Smipe · 25.07.2021, 13:34 **[ТС]**

Puporev, сортировать с запоминанием индекса. То есть сортируем значения, а вместе с ними меняем индексы

@vantfiles · 25.07.2021, 13:36

Можно и в один, кстати проход, сразу считать разницу последних двух индексов и запоминать минимальную

@Smipe · 25.07.2021, 13:41 **[ТС]**

vantfiles, пока не понимаю как за 1 проход можно посчитать. Где Вы выше написали подход, там сложность O(n+k)?, где n изначальный размер массива и k количество повторяющихся элементов?

@vantfiles · 25.07.2021, 13:56

O(n) получается, сложность - это асимптотика, а не конкретные цифры.

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

Добавлено через 7 минут
Вот код на с++: (не мой)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef pair<bool, int> LastPositionFound;
 
int MinPair(const std::vector<int>& nums)
{
    unordered_map<int, LastPositionFound> table; // maps value found in array to the last position that value was seen at.
    int best_distance = -1;
 
    for (size_t index = 0; index < nums.size(); index++)
    {
        int value = nums[index];
        LastPositionFound& lpf = table[value];  // returns {false,0} if not found
        if (lpf.first)
        {
            int distance = index - lpf.second;
            if ((distance < best_distance) || (best_distance == -1))
            {
                best_distance = distance;
            }
        }
 
        // update reference to hash table entry
        lpf.first = true;
        lpf.second = index;
    }
    return best_distance;
}

@Smipe · 25.07.2021, 13:56 **[ТС]**

vantfiles, все, понял. Спасибо большое!

@vantfiles · 25.07.2021, 13:58

Это немного не то, что требуется в задании, но идея та же.

@Mikhaylo · 25.07.2021, 16:49

Сообщение от vantfiles

На первом проходе складываем числа в список:
<...>
На втором ищем минимальную разницу.

Алгоритм занимает много памяти... Сложность по памяти O(n). Есть куда стремиться.

@vantfiles · 25.07.2021, 17:50

Сообщение от Mikhaylo

Есть куда стремиться.

Даже если хранить только последние два индекса, все равно в исходном массиве может попросту не оказаться совпадений.
Можете предложить направление, куда стремиться? Хотите экономию по памяти - в процессе сканирования затирайте исходный массив.

@Shamil1 · 26.07.2021, 16:23

Сообщение от vantfiles

в процессе сканирования затирайте исходный массив

Это как? Память, выделенную под массив, можно освободить только сразу всю.

@vantfiles · 27.07.2021, 07:41

Сообщение от Shamil1

Это как? Память, выделенную под массив, можно освободить только сразу всю.

void * realloc( void * ptrmem, size_t size );

@Shamil1 · 28.07.2021, 00:40

Сообщение от vantfiles

void * realloc( void * ptrmem, size_t size );

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

@vantfiles · 28.07.2021, 10:52

Сообщение от Shamil1

не кажется мне хорошей идеей

Разумеется. Нет, программе то эта память будет доступна - а вот системе она не вернется.
Просто человек пошутил насчет экономии памяти, я пошутил насчет способа экономии.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@Smipe 1 / 1 / 0 Регистрация: 13.10.2020 Сообщений: 10

	Поиск индексов одинаковых элементов 25.07.2021, 13:00. Показов 2763. Ответов 15 Метки arrays, c++, hash, merge sort, индексы, массивы, сортировка, хеш, хеш-функции (Все метки) Напишите псевдокод алгоритма, который находит в массиве два одинаковых элемента, расстояние между которыми в массиве минимально. То есть нужно найти индексы i, j такие, что: $https://www.cyberforum.ru/cgi-bin/latex.cgi?i^, j^ = argmin\{j - i \| a_i = a_j, i < j\}$ Покажите, какую вычислительную сложность имеет ваш алгоритм и почему. Считайте, что размер массива не более 10^7, а элементы массива - целые числа от -10^18 до 10^18. Первое решение, что пришло в голову это перебрать каждый элемент за O(n^2) и запомнить индексы одинаковых элементов и их разницу и так искать минимальное расстояние. Второе решение, это отсортировать a_i по возрастанию и дальше сравнивать по 2 числа Например: list index: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18] list value: [2, 7, 1, 2, 4, 2, 9, 10, 7, 2, 4, 4, 10, 1, 8, 2, 5, 9, 6] Сортируем и получаем такое list index: [2, 13, 0, 3, 5, 9, 15, 4, 10, 11, 16, 18, 1, 8, 14, 6, 17, 7, 12] list value: [1, 1, 2, 2, 2, 2, 2, 4, 4, 4, 5, 6, 7, 7, 8, 9, 9, 10, 10] Сравниваем по 2 элемента и запоминаем разницу индексов, потом находим минимальное значение Сложность O(n log n). Как решить эту задачу за O(n)? 0

@vantfiles 1018 / 1914 / 177 Регистрация: 07.05.2013 Сообщений: 3,931 Записей в блоге: 12
	25.07.2021, 13:30
	Да, как только найдется пара с разницей в 1, дальше можно не крутить - все равно меньше не будет. 0

@Smipe 1 / 1 / 0 Регистрация: 13.10.2020 Сообщений: 10
	25.07.2021, 13:34 [ТС]
	Puporev, сортировать с запоминанием индекса. То есть сортируем значения, а вместе с ними меняем индексы 0

@vantfiles 1018 / 1914 / 177 Регистрация: 07.05.2013 Сообщений: 3,931 Записей в блоге: 12
	25.07.2021, 13:36
	Можно и в один, кстати проход, сразу считать разницу последних двух индексов и запоминать минимальную 0

@Smipe 1 / 1 / 0 Регистрация: 13.10.2020 Сообщений: 10
	25.07.2021, 13:41 [ТС]
	vantfiles, пока не понимаю как за 1 проход можно посчитать. Где Вы выше написали подход, там сложность O(n+k)?, где n изначальный размер массива и k количество повторяющихся элементов? 0

@Smipe 1 / 1 / 0 Регистрация: 13.10.2020 Сообщений: 10
	25.07.2021, 13:56 [ТС]
	vantfiles, все, понял. Спасибо большое! 0

@vantfiles 1018 / 1914 / 177 Регистрация: 07.05.2013 Сообщений: 3,931 Записей в блоге: 12
	25.07.2021, 13:58
	Это немного не то, что требуется в задании, но идея та же. 0

Поиск индексов одинаковых элементов

Решение