найти что-то не так с моим кодом, решить простую конкурентную задачу

Question

QN; вот вопрос. Я не знаю, где мой алгоритм неверен. Помогите мне найти pls

Учитывая массив A длины N. Нам нужно вычислить следующий больший элемент для каждого элемента в данном массиве. Если следующий больший элемент недоступен в данном массиве, нам нужно заполнить '_' в этом месте индекса.

Входные данные: Первая строка содержит целое число T, количество тестовых случаев. Для каждого теста первая строка содержит целое число n, размер массива. Следующая строка содержит n разделенных пробелом целых чисел, обозначающих элементы массива.

Вывод: для каждого тестового примера вывод представляет собой массив, который отображает следующий больший элемент к элементу с этим индексом.

Constraints:
1 <= T <= 100
1 <= N <= 100
-106 <= Ai <= 106

Example:
Input
2
9
6 3 9 8 10 2 1 15 7
4
13 6 7 12

Output:
7 6 10 9 15 3 2 _ 8
_ 7 12 13

Объяснение: Тестовый случай 1: Здесь каждый элемент массива имеет следующий больший элемент, но по индексу 7, 15 - это самый большой элемент данного массива, и ни один другой элемент не больше 15, поэтому при индексе 15 мы заполняем ''. Тестовый пример 2: здесь, с индексом 0, 13 является наибольшим значением в данном массиве, и никакой другой элемент массива не больше 13, поэтому в индексе 0 мы заполняем ''.

Мое решение:

//NOT SOLVED YET
#include<iostream>
using namespace std;
int main()
{
    int a[10]={6 ,3 ,9, 8 ,10, 2 ,1, 15, 7};
    int b[10],flag=0,big=-1,i,j;
    for(i=0;i<10;i++)
    {
        for(j=0;j<10;j++)
        {
            if(i==j)continue;
            if((a[j]>a[i]) && (flag==0))
            {
                big=a[j];
                flag=1;
            }
            else if(a[j]<big && big>a[i] && flag==1)
                big=a[j];

        }
        if(big==-1)cout<<'_';
        else cout<<big<<' ';
        big=-1;
        flag=0;
    }

}

вывод, который я получаю:

 2 2 2 2 7 1 0 _ 2 1

Answer 1

Условие должно быть:

    else if(a[j] < big && <b>a[j]</b> > a[i] && flag == 1)

Действительно, если вы используете big > a[i], то это означает, что вы просто проверяете, был ли , таким образом, следующий следующий больший элемент больше, чем a[i], но это, таким образом, позволяет в дальнейшем выбрать значение, которое меньше, чем big, но также меньше, чем a[i]. Таким образом, здесь мы хотим проверить, находится ли a[j] между a[i] и big.

При этом вышеупомянутый подход не очень эффективен. Действительно, для каждого элемента вы вычисляете следующий элемент за линейное время, делая этот алгоритм quadrati c времени. Возможно, вы захотите посмотреть на решения, где список сортируется первым. Например, вы можете использовать min-heap здесь для перемещения по списку в два прохода.

Answer 2

Чтобы расширить то, что упоминали другие - что у вас в настоящее время есть алгоритм O (N ^ 2), и это можно сделать более эффективно.

Я не думаю, что вы можете получить O (N) здесь, но вот план для алгоритма O (N log N):

Для каждого теста:

• Загрузите значения Ai в два массива, назовем их X и Y
• Сортировка массива Y
• Итерация по X и для каждого элемента X выполните двоичный поиск в Y, чтобы найти следующее большее значение Ai: используйте его в качестве выходного или используйте _ если вы не нашли один

, я рекомендую для практических целей реализовать оба варианта с использованием стандартной библиотеки C ++, используя https://en.cppreference.com/w/cpp/algorithm/sort и https://en.cppreference.com/w/cpp/algorithm/upper_bound и самостоятельно реализуйте две вышеуказанные функции, см .: https://en.wikipedia.org/wiki/Quicksort