Поиск наименьшего следующего большего элемента ⇐ C++
-
Anonymous
Поиск наименьшего следующего большего элемента
У меня есть задача, которая требует от меня найти наименьший из всех больших элементов в массиве для всех записей массива и сохранить соответствующие индексы в массиве, и я не могу понять последнюю часть решения.
Это похоже на проблему, описанную здесь: https://www.geeksforgeeks.org/smallest- ... ole-array/
Единственное отличие состоит в том, что учитываются только значения справа от элемента массива (j>i), например:
ввод: [80; 19; 49; 45; 65; 71; 76; 28; 68; 66] вывод: [-1; 7; 4; 4; 9; 6; -1; 9; -1; -1] Мне кажется разумным решение с использованием самобалансирующегося дерева. Однако мне все равно нужно учитывать индексацию, поскольку действительны только решения справа от записи массива.
Есть ли способ сопоставить индексацию вставленных значений с записями дерева или создать второе дерево с идентичной структурой, но с индексом старых записей массива вместо фактических значений в качестве узлов? Я не уверен, потому что структура самобалансирующегося дерева, конечно, зависит от вставленных значений (правое поддерево с большими значениями, левое поддерево с меньшими значениями).
РЕДАКТИРОВАТЬ: На самом деле второе дерево AVL, возможно, не поможет, поскольку мне нужно проверить, что индексация больше И запись массива больше при обходе дерева...
У меня есть задача, которая требует от меня найти наименьший из всех больших элементов в массиве для всех записей массива и сохранить соответствующие индексы в массиве, и я не могу понять последнюю часть решения.
Это похоже на проблему, описанную здесь: https://www.geeksforgeeks.org/smallest- ... ole-array/
Единственное отличие состоит в том, что учитываются только значения справа от элемента массива (j>i), например:
ввод: [80; 19; 49; 45; 65; 71; 76; 28; 68; 66] вывод: [-1; 7; 4; 4; 9; 6; -1; 9; -1; -1] Мне кажется разумным решение с использованием самобалансирующегося дерева. Однако мне все равно нужно учитывать индексацию, поскольку действительны только решения справа от записи массива.
Есть ли способ сопоставить индексацию вставленных значений с записями дерева или создать второе дерево с идентичной структурой, но с индексом старых записей массива вместо фактических значений в качестве узлов? Я не уверен, потому что структура самобалансирующегося дерева, конечно, зависит от вставленных значений (правое поддерево с большими значениями, левое поддерево с меньшими значениями).
РЕДАКТИРОВАТЬ: На самом деле второе дерево AVL, возможно, не поможет, поскольку мне нужно проверить, что индексация больше И запись массива больше при обходе дерева...
