gabbek
Jun '15

Witam serdecznie, zastanawiam się o jaką złożoność mógłbym się pokusić dysponując jedną tablicą, bądź wczytując po prostu kolejne wartości:
[bbone=CPP,2995]int T[7] = { 7, 2 , 1, 4, 3, 6, 5 };[/bbone]
Jeśli chciałbym zrobić tablicę lub też od razu zliczać całkowitą ilość (w tym przypadku sumaMniejszych = 6+1+1+1 = 9), która pod i-tym indeksem przechowuje ilość liczb mniejszych od wartości i-tej z tablicy T po prawej stronie! (bardzo ważne), a więc chciałbym uzyskać drugą tablicę o wartościach:
[bbone=CPP,2996]int A[7] = { 6, 1, 0, 1, 0, 1, 0};[/bbone]
Prosiłbym o pomoc, z góry dziękuje za sugestie smile

-- Pn cze 01, 2015 7:01 pm --

Pomysł #1 dotyczący zliczenia sumy, zamiast tworzenia tablicy A.
Niech SUMA oznacza naszą zmienną, w której będziemy trzymać interesujący nas wynik.
Tworzymy sobie listę dwukierunkową z dostępem do pierwszego i ostatniego elementu, w której kolejne elementy będą większe lub równe poprzedniemu. Następnie wczytujemy po kolei kolejne liczby, jeśli w naszej liście istnieje liczba większa od wczytanej w danej chwili to przemieszczamy się od ostatniego elementu dopóki element w liście nie jest równy bądź mniejszy od naszego wczytanego.

Np: (wczytaliśmy już do listy 3 4 5), a następną wczytywaną liczbą jest 3. Istnieje w tablicy liczba większa od naszej - 5. Przemieszczamy się 5 -> 4 -> 3, następnie dołączamy naszą drugą trójkę to listy, a do SUMY dopisujemy (ilość elementów - przejścia, w tym przypadku 3-2=1), tak działy aż nie wczytamy wszystkich liczb.

Problem tkwi w tym, iż ten mój pomysł nie jest nawet bliski złożoności O(N), hmm...

  • created

    Jun '15

  • last reply

    Jun '15
  • 1

    reply

  • 707

    views

  • 2

    users

narbej
Jun '15

Nie wiem, czy dobrze zrozumiałem twój problem, może go trochę źle, za mało, go opisałeś?
Gdy chodzi tylko o tablicę A:
int A[7] = { 6, 1, 0, 1, 0, 1, 0};
To można ją utworzyć, od tyłu, korzystając dodatkowo np z drzewa licznikowego [przedziałowego]. Przy takim tworzeniu, jezeli tablica nie jest do niczego już więcej potem potrzebna, wynikową tablicę A można tworzyć "in place" w tablicy T.
int T[7] = { 7, 2 , 1, 4, 3, 6, 5 };
1. Bierzemy [od końca] kolejną liczbę z tab T.
2. Sprawdzamy ile jest liczb z przedziału [0, liczba-1] w drzewie
3. wstawiamy ile do tablicy A [lub T] na odpowiedniej pozycji.
4. wstawiamy liczba do drzewa [dodajemy jeden na pozycji liczba]
5. goto 1
Możliwe, że chodzi Ci o tablicę [sum prefiksowych ]:
A' [7] = { 9, 3, 2, 2, 1, 1, 0};
Jeżeli tak, to żaden problem i możesz ją skonstruować potem albo najlepiej od razu.