the requirement is a little bit complicated let's say we have an unsorted array, for example: {12, 72, 93, 0, 24, 56, 102}

if we have an odd position, we have to look for the next greater element in his right, let's say we take v[1] = 12, the nge for '12' is 24;

but if we have an even position, we have to look for the next greater element in his left, let's say we take v[2] = 72, there s no number who s greater than '72', so we will print '-1'; let's take another example, v[4] = 0, the nge for '0' is 12;

the output should be: 24 -1 102 12 56 72 -1

i tried to solve this in c :

#include <iostream>
using namespace std;

int main() {
    const int CONST = 10000;
    int n, v[CONST];
    cin >> n;
    for (int i = 1; i <= n; i  ) {
        cin >> v[i];
    }
    for (int i = 1; i <= n; i  ) {
        int next = -1;
        if (i % 2 != 0) {   
            for (int j = i   1; j <= n; j  ) {
                if (v[j] > v[i]) {
                    next = v[j];
                    break;
                }
            }
            cout << next << " ";
        }
        else {                
            for (int k = 1; k <= i - 1; k  ) {
                if (v[k] > v[i]) {
                    next = v[k];
                    break;
                }
            }
            cout << next << " ";
        }
    }
    return 0;
}

firstly, i think that i have to sort the array and after that to use binary search for finding the next greater element

CodePudding user response：

For starters instead of the array it is much better to declare an object of the type std::vector<int>.

Pay attention to that indices in C start from 0.

In this if statement

            if (v[j] > v[i]) {
                next = v[j];
                break;
            }

you are exiting the loop as soon as the first element greater than the current is found. It is evident that this approach is wrong.

I can suggest the following solution.

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v;
    size_t n = 0;

    std::cin >> n;

    v.resize( n );

    for (auto &item : v)
    {
        std::cin >> item;
    }

    for (size_t i = 0, n = v.size(); i < n; i  )
    {
        size_t next = i;

        if (i % 2 == 0)
        {
            for (size_t j = i   1; j != n;   j)
            {
                if (v[i] < v[j] && ( next == i || v[j] < v[next] ))
                {
                    next = j;
                }
            }
        }
        else
        {
            for (size_t j = i; j-- != 0; )
            {
                if (v[i] < v[j] && ( next == i || v[j] < v[next] ))
                {
                    next = j;
                }
            }
         }

         std::cout << ( next != i ? v[next] : -1 ) << ' ';
    }
}

The program output might look like

7
12 72 93 0 24 56 102
24 -1 102 12 56 72 -1

CodePudding user response：

If you are looking for something simple yet not very efficient (e.g. O(n) space complexity -vector copy- and O(nlogn) time complexity -sort plus search- instead of an O(n) for a linear search), this is an option:

• next_greater checks if pos is even or odd, creates a couple of iterators first and last, and calls a templated next_greater with those iterators and the value to compare against, n.
• a templated next_greater sorts [first, last) and then uses upper_bound to return the first element that is greater than n.

[Demo]

#include <algorithm>  // upper_bound
#include <iostream>  // cout
#include <utility>  // pair
#include <vector>

template <typename InputIt, typename T>
T next_greater(InputIt first, InputIt last, T n)
{
    std::sort(first, last);
    auto it{ std::upper_bound(first, last, n) };
    if (it == last) { return -1; }
    return *it;
}

int next_greater(std::vector<int> v, size_t pos)
{
    using it = std::vector<int>::iterator;
    using pair_it = std::pair<it, it>;

    auto [first, last] { (pos % 2 == 1)
        ? pair_it{ std::begin(v), std::begin(v)   pos }  // [begin, pos)
        : pair_it{ std::begin(v)   pos   1, std::end(v) }  // [pos   1, end)
    };
    return next_greater(first, last, v[pos]);  
}

int main()
{
    const std::vector<int> v{12, 72, 93, 0, 24, 56, 102};
    std::cout << "Next greater for i(n):\n";
    for (size_t i{0}; i < v.size();   i)
    {
        std::cout << "\t" << i << "(" << v[i] << "): " << next_greater(v, i) << "\n";
    }
}

// Outputs:
//
//   Next greater for i(n):
//      0(12): 24
//      1(72): -1
//      2(93): 102
//      3(0): 12
//      4(24): 56
//      5(56): 72
//      6(102): -1