Kolejna Większa Liczba

Odpowiedz Nowy wątek
2019-04-28 21:50
0

Dana jest tablica. Kolejną Większą Liczbą liczby x jest najbliższa (przeglądając kolejne elementy w prawą stronę) większa od niej liczba występująca w tablicy. Jeśli KWL dla x nie istnieje, wypisz -1 dla tego numeru. Należy założyć, że tablica jest “cykliczna”, tzn po osiągnięciu ostatniego elementu wyszukiwanie kontynuowane jest od indeksu 0.

Wejście: [1, 2, 1, 4, 1]
Wyjście: [2, 4, 4, -1, 2]

Zgodnie z: https://stackoverflow.com/que[...]-in-an-array-for-each-element
udało mi sie napisać taki kod:

#include <iostream>
#include <stack>
#include <vector>

int get(std::stack<int> &s){
    int x = s.top();
    s.pop();
    return x;
}

int main(){

    std::stack<int> s;
    std::vector<int> data{1,2,1,4,1};

    s.push(data.at(0));
    data.erase(data.begin());
    for(int x : data){
        if(!s.empty()){
            while(true){
                if(s.empty() || s.top() > x){
                    break;
                }

                std::cout << get(s) << " : " << x << std::endl;
            }
        }

        s.push(x);
    }

    while(!s.empty()){
        std::cout << get(s) << " : -1\n";
    }

    return 0;
}

Jednak daje złą odpowiedź oraz jest jakoś porozwalane
asdf

Prosze o pomoc

Pozostało 580 znaków

2019-04-28 22:20
0

Zestaw sobie data.erase(data.begin()); z Należy założyć, że tablica jest “cykliczna”.

Edit: strasznie to wszystko przekomplikowałeś tak w ogóle: https://ideone.com/Y53Bqw.


edytowany 2x, ostatnio: Patryk27, 2019-04-28 22:26

Pozostało 580 znaków

2019-04-28 22:28
0

Zmieniłem kod

nadal to samo. A Twój kod to jest zwykły bruteforce w n^2. Chciałbym, żeby to działało w czasie liniowym

edytowany 1x, ostatnio: newbier123, 2019-04-28 22:44
A Twój kod to jest zwykły bruteforce w n^2. Chciałbym, żeby to działało w czasie liniowym - nic takiego w swoim pierwszym poście nie napisałeś + podejście ze stosem nie jest liniowe ;-p - Patryk27 2019-04-28 22:28
Standardowe podejście ze stosem jest O(N). - Mózg 2019-04-29 14:45

Pozostało 580 znaków

2019-04-28 22:43
0

W sumie zrobiłem teraz coś takiego:

#include <iostream>
#include <stack>
#include <vector>

typedef std::pair<int, int> item;

item get(std::stack<item> &s){
    item x = s.top();
    s.pop();
    return x;
}

int main(){

    std::stack<item> s; //index, val
    std::vector<int> data{1,2,1,4,1}; //[2, 4, 4, -1, 2]
    int size = data.size();
    std::vector<int> o(size);

    s.push(std::make_pair(0, data.at(0)));
    for(int i = 1; i < size-1; i++){
        int x = data[i];
        if(!s.empty()){
            while(true){
                if(s.empty() || s.top().second > x){
                    break;
                }
                o.at(get(s).first) = x;
                //std::cout << i.second << " : " << x << std::endl;
            }
        }

        s.push(std::make_pair(i, x));
    }

    while(!s.empty()){
        o.at(get(s).first) = -1;
        //std::cout << i.second << " : -1\n";
    }

    o.at(size-1) = -1;
    for(int i = 0; i < size-1; i++){
        if(data[i] > data[size-1]){
            o.at(size-1) = data[i];
            break;
        }
    }

    std::cout << '\n';

    for(int i = 0; i < size; i++){
        std::cout << data[i] << " : " << o[i] << '\n'; 
    }

    return 0;
}

I działa, ale dla ostatniego przechodze całą tablice, nie wiem jak inaczej to zrobić. Troche lamersko ....

Pozostało 580 znaków

2019-04-29 05:10

Ależ ja dawno w C++ nie pisałem :D

#include <iostream>
#include <stack>
#include <vector>

int main() {

    std::stack<int> stackOfIndexes;
    std::vector<int> data{ 1,2,1,4,1 };
    std::vector<int> result(data.size());
    std::fill(result.begin(), result.end(), -1);
    std::vector<int> doubleData = data;
    copy(data.begin(), data.end(), back_inserter(doubleData));

    for (int i = 0; i < doubleData.size(); ++i)
    {       
        while (!stackOfIndexes.empty() && doubleData[stackOfIndexes.top()] < doubleData[i])
        {
            result[stackOfIndexes.top()] = doubleData[i];
            stackOfIndexes.pop();
        }

        if (i < data.size())
        {
            stackOfIndexes.push(i);
        }
    }

    for (int i = 0; i < data.size(); ++i)
    {
        std::cout << data[i] << " : " << result[i] << std::endl;
    }   

    return 0;
}

Pozostało 580 znaków

2019-04-29 12:49
0

A mógłbyś wyjaśnić na czym polega ten sposób?

Pozostało 580 znaków

2019-04-29 13:04
0

To jest dokładnie zmodyfikowany Twój kod implementujący rozwiązanie ze stackoveflow.
Plus dodałem dwa tricki, które uprościły znacznie kod:

  • "ale dla ostatniego przechodzę całą tablice, nie wiem jak inaczej to zrobić.", inaczej można to zrobić przez skopiowanie oryginalnej tablicy x2, dzięki temu mamy jedną pętle przechodzącą dwa razy tą samą tablicę, zauważ że trochę inaczej przetwarzamy pierwszą połowę/kopię od drugiej połowy/kopi - nie dodajemy już wtedy na stos
  • zamiast trzymać wartości, czy pary na stosie, wystarczy nam indeks z oryginalnej tablicy zawierającej dane wejściowe

złożoność O(3*n)

edytowany 2x, ostatnio: neves, 2019-04-29 13:15
O(2n) = O(n) - Patryk27 2019-04-29 13:10
przy czym ta wewnętrzna pętla while sugeruje raczej złożoność w kierunku O(n log n) / O(n^2) - Patryk27 2019-04-29 13:11
wewnętrzna pętla wykona się maksymalnie n razy, więc jest to maks liniowe, żadne kwadraty czy liniowe logarytmy :P, poprawiłem złożoność by to uwypuklić - neves 2019-04-29 13:15
nie ma czegoś takiego, jak O(3n), jest po prostu O(n); chodzi mi o to, że masz jedną pętlę, która wykonuje się O(i) razy oraz wewnątrz niej masz drugą, która pesymistycznie może wykonać się następne O(i) razy - daje to pesymistycznie O(i*i), czyli złożoność kwadratową. Liniowa występuje tylko w najbardziej optymistycznej sytuacji, kiedy wewnętrzny while obróci się raz dla każdego i. - Patryk27 2019-04-29 13:18
jest to nieformalny zapis często używany w competitive programming żeby dokładniej podkreślić liczbę operacji, zauważ że na stosie może być maksymalnie dodane n elementów przez cały czas działania programu i za każdym obrotem pętli zdejmujemy element ze stosu, więc wewnętrzna pętla w pesymistycznym przypadku wykona się n razy, więc to daje n+n a nie n*n ;) - neves 2019-04-29 13:28
niech to dunder świśnie, brzmi sensownie :-) - Patryk27 2019-04-29 13:51

Pozostało 580 znaków

2019-04-29 13:37
1
template<typename It, typename F>
auto cycle_find_if(It b, It e, It start, F &&f) -> It
{
    auto i = std::find_if(start, e, f);
    if (i != e) return i;
    i = std::find_if(b, start, std::forward<F>(f));
    return i != start ? i : e;
}

int cycleFindFirstGreater(const std::vector<int>& v, int index)
{
    auto x = v[index];
    auto it = cycle_find_if(v.begin(), v.end(), v.begin() + index, [x](auto a) { return a > x; });
    return it != v.end() ? *it : -1;
}

Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0