Jak rozwiązać zadanie, aby złożoność obliczeniowa była jak najmniejsza?

Jak rozwiązać zadanie, aby złożoność obliczeniowa była jak najmniejsza?
bakeraw2
  • Rejestracja:prawie 14 lat
  • Ostatnio:ponad 5 lat
  • Postów:400
0

Dostałem ostatnio takie zadanie i z ciekawości zastanawiam się jak je rozwiązać, żeby złożoność obliczeniowa była jak najmniejsza.

Mamy dość sporą tablicę liczb typu int. Tablica jest nieposortowana i każdy element w tablicy poza jednym ma parę w postaci tej samej wartości,
czyli np {1, 2, 1, 3, 2} i trzeba znaleźć liczbę która nie ma pary.

Ja rozwiązałem to poprzez przerzucenie wartośći tablicy do HashMapy typu generycznego < Integer, Integer >
kluczem jest liczba a wartością ile razy wystąpiła. Na końcu przeglądam mapę w poszukiwaniu liczby która wystąpiła raz.

Macie jakiś lepszy pomysł? :)

edytowany 1x, ostatnio: bakeraw2
somekind
Zmień tytuł zanim wątek poleci do kosza.
olesio
Poprawiłem. Ale następnym razem @somekind bez zastanowienia koszuj. Tymbardziej, że user nie jest na forum po raz pierwszy. Nie chce się dostosować do zasad, to nie nasz problem.
bakeraw2
Ok spokojnie następnym razem zrobię to lepiej ;)
freemp3
  • Rejestracja:około 11 lat
  • Ostatnio:około 5 godzin
  • Lokalizacja:Miechów
  • Postów:284
0
  1. Tworzysz obiekt typu ArrayList<int>
  2. Lecisz pętlą po tablicy i sprawdzasz czy liczba jest już dodana, jeśli nie to dodajesz, jeśli tak to usuwasz.
  3. Na końcu pętli powinna zostać tablica z jednym elementem, tym który nie ma pary.

twonek
Usuwanie z ArrayList jest kosztowne, więc to jest mocno nieoptymalny algorytm.
bakeraw2
  • Rejestracja:prawie 14 lat
  • Ostatnio:ponad 5 lat
  • Postów:400
0

Chyba już nic lepszego się nie znajdzie nie? :)

datdata
  • Rejestracja:prawie 11 lat
  • Ostatnio:prawie 7 lat
  • Postów:957
1

Tworzysz pusty HashSet i iterujesz po tablicy: sprawdzasz czy element istnieje w secie - jeśli nie to wrzucasz element do seta, jeśli istnieje to go wyrzucasz. Na końcu masz set z jednym elementem.

Minimalnie wydajniejsze od Twojego powinno być, a na pewno ładniejsze ;)

EDIT: Nie zauważyłem poprzednich odpowiedzi. Idea ta sama, ale za używanie do tego ArrayList powinno się bić po twarzy.


"A human being should be able to change a diaper, plan an invasion, butcher a hog, conn a ship, design a building, write a sonnet, balance accounts, build a wall, set a bone, comfort the dying, take orders, give orders, cooperate, act alone, solve equations, analyze a new problem, pitch manure, program a computer, cook a tasty meal, fight efficiently, die gallantly. Specialization is for insects." Robert Heinlein.
edytowany 1x, ostatnio: datdata
bakeraw2
Dzięki, to wydaje się być najlepsze ;)
bogdans
Moderator
  • Rejestracja:prawie 17 lat
  • Ostatnio:prawie 5 lat
3

Z moich eksperymentów wynika, że szybszy jest kod bez sprawdzania czy element jest w secie.

Kopiuj
if(!set.remove(i))
    set.add(i);

jest szybsze niż

Kopiuj
if(set.contains(i))
    set.remove(i);
else    
    set.add(i);

To smutne, że głupcy są tak pewni siebie, a ludzie mądrzy - tak pełni wątpliwości. Bertrand Russell
Shalom
Nie dziwota bo przeciez contains()+remove() wymaga powtórzenia tych samych operacji (dwa razy liczymy hash i rozwiązujemy konflikty). Różnica tylko taka że remove() po znalezieniu elementu usuwa go z tablicy a contains() zwraca od razu true. Więc takie kombo będzie 2 razy wolniejsze chyba że JVM to jakoś magicznie wrzuci w cache, ale wątpie.
_13th_Dragon
Tego chyba należało się spodziewać ponieważ .constins() musi tak samo wyszukać jak .remove().
_13th_Dragon
  • Rejestracja:ponad 19 lat
  • Ostatnio:2 miesiące
7
bakeraw2 napisał(a):

Chyba już nic lepszego się nie znajdzie nie? :)

Ależ skąd:

Kopiuj
import java.io.*;

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int[] tb={1, 2, 1, 3, 2};
		int result=0;
		for(int i:tb) result^=i;
		System.out.println(result);
	}
}

http://ideone.com/gcLhTy


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.
Zobacz pozostały 1 komentarz
_13th_Dragon
@datdata, kompletnie nie rozumiem komentarzu.
datdata
W sensie, że to rozwiązanie jest najlepsze.
_13th_Dragon
Nie ;P Bo to ze SPOJ'a. Autor tematu podał już zadanie przerobione wg swego rozumienia, w samym zadaniu da się jeszcze lepiej.
datdata
Jak brzmi standardowa wersja?
_13th_Dragon
Te liczby są podawane z wejścia standardowego.
WK
WK
  • Rejestracja:około 11 lat
  • Ostatnio:prawie 10 lat
  • Postów:110
0

Najszybszym znanym mi sposobem rozwiazania tego typu problemu jest Bloom filter

_13th_Dragon
No to poczytaj post powyżej będziesz znać o wiele szybszy.
Kliknij, aby dodać treść...

Pomoc 1.18.8

Typografia

Edytor obsługuje składnie Markdown, w której pojedynczy akcent *kursywa* oraz _kursywa_ to pochylenie. Z kolei podwójny akcent **pogrubienie** oraz __pogrubienie__ to pogrubienie. Dodanie znaczników ~~strike~~ to przekreślenie.

Możesz dodać formatowanie komendami , , oraz .

Ponieważ dekoracja podkreślenia jest przeznaczona na linki, markdown nie zawiera specjalnej składni dla podkreślenia. Dlatego by dodać podkreślenie, użyj <u>underline</u>.

Komendy formatujące reagują na skróty klawiszowe: Ctrl+B, Ctrl+I, Ctrl+U oraz Ctrl+S.

Linki

By dodać link w edytorze użyj komendy lub użyj składni [title](link). URL umieszczony w linku lub nawet URL umieszczony bezpośrednio w tekście będzie aktywny i klikalny.

Jeżeli chcesz, możesz samodzielnie dodać link: <a href="link">title</a>.

Wewnętrzne odnośniki

Możesz umieścić odnośnik do wewnętrznej podstrony, używając następującej składni: [[Delphi/Kompendium]] lub [[Delphi/Kompendium|kliknij, aby przejść do kompendium]]. Odnośniki mogą prowadzić do Forum 4programmers.net lub np. do Kompendium.

Wspomnienia użytkowników

By wspomnieć użytkownika forum, wpisz w formularzu znak @. Zobaczysz okienko samouzupełniające nazwy użytkowników. Samouzupełnienie dobierze odpowiedni format wspomnienia, zależnie od tego czy w nazwie użytkownika znajduje się spacja.

Znaczniki HTML

Dozwolone jest używanie niektórych znaczników HTML: <a>, <b>, <i>, <kbd>, <del>, <strong>, <dfn>, <pre>, <blockquote>, <hr/>, <sub>, <sup> oraz <img/>.

Skróty klawiszowe

Dodaj kombinację klawiszy komendą notacji klawiszy lub skrótem klawiszowym Alt+K.

Reprezentuj kombinacje klawiszowe używając taga <kbd>. Oddziel od siebie klawisze znakiem plus, np <kbd>Alt+Tab</kbd>.

Indeks górny oraz dolny

Przykład: wpisując H<sub>2</sub>O i m<sup>2</sup> otrzymasz: H2O i m2.

Składnia Tex

By precyzyjnie wyrazić działanie matematyczne, użyj składni Tex.

<tex>arcctg(x) = argtan(\frac{1}{x}) = arcsin(\frac{1}{\sqrt{1+x^2}})</tex>

Kod źródłowy

Krótkie fragmenty kodu

Wszelkie jednolinijkowe instrukcje języka programowania powinny być zawarte pomiędzy obróconymi apostrofami: `kod instrukcji` lub ``console.log(`string`);``.

Kod wielolinijkowy

Dodaj fragment kodu komendą . Fragmenty kodu zajmujące całą lub więcej linijek powinny być umieszczone w wielolinijkowym fragmencie kodu. Znaczniki ``` lub ~~~ umożliwiają kolorowanie różnych języków programowania. Możemy nadać nazwę języka programowania używając auto-uzupełnienia, kod został pokolorowany używając konkretnych ustawień kolorowania składni:

```javascript
document.write('Hello World');
```

Możesz zaznaczyć również już wklejony kod w edytorze, i użyć komendy  by zamienić go w kod. Użyj kombinacji Ctrl+`, by dodać fragment kodu bez oznaczników języka.

Tabelki

Dodaj przykładową tabelkę używając komendy . Przykładowa tabelka składa się z dwóch kolumn, nagłówka i jednego wiersza.

Wygeneruj tabelkę na podstawie szablonu. Oddziel komórki separatorem ; lub |, a następnie zaznacz szablonu.

nazwisko;dziedzina;odkrycie
Pitagoras;mathematics;Pythagorean Theorem
Albert Einstein;physics;General Relativity
Marie Curie, Pierre Curie;chemistry;Radium, Polonium

Użyj komendy by zamienić zaznaczony szablon na tabelkę Markdown.

Lista uporządkowana i nieuporządkowana

Możliwe jest tworzenie listy numerowanych oraz wypunktowanych. Wystarczy, że pierwszym znakiem linii będzie * lub - dla listy nieuporządkowanej oraz 1. dla listy uporządkowanej.

Użyj komendy by dodać listę uporządkowaną.

1. Lista numerowana
2. Lista numerowana

Użyj komendy by dodać listę nieuporządkowaną.

* Lista wypunktowana
* Lista wypunktowana
** Lista wypunktowana (drugi poziom)

Składnia Markdown

Edytor obsługuje składnię Markdown, która składa się ze znaków specjalnych. Dostępne komendy, jak formatowanie , dodanie tabelki lub fragmentu kodu są w pewnym sensie świadome otaczającej jej składni, i postarają się unikać uszkodzenia jej.

Dla przykładu, używając tylko dostępnych komend, nie możemy dodać formatowania pogrubienia do kodu wielolinijkowego, albo dodać listy do tabelki - mogłoby to doprowadzić do uszkodzenia składni.

W pewnych odosobnionych przypadkach brak nowej linii przed elementami markdown również mógłby uszkodzić składnie, dlatego edytor dodaje brakujące nowe linie. Dla przykładu, dodanie formatowania pochylenia zaraz po tabelce, mogłoby zostać błędne zinterpretowane, więc edytor doda oddzielającą nową linię pomiędzy tabelką, a pochyleniem.

Skróty klawiszowe

Skróty formatujące, kiedy w edytorze znajduje się pojedynczy kursor, wstawiają sformatowany tekst przykładowy. Jeśli w edytorze znajduje się zaznaczenie (słowo, linijka, paragraf), wtedy zaznaczenie zostaje sformatowane.

  • Ctrl+B - dodaj pogrubienie lub pogrub zaznaczenie
  • Ctrl+I - dodaj pochylenie lub pochyl zaznaczenie
  • Ctrl+U - dodaj podkreślenie lub podkreśl zaznaczenie
  • Ctrl+S - dodaj przekreślenie lub przekreśl zaznaczenie

Notacja Klawiszy

  • Alt+K - dodaj notację klawiszy

Fragment kodu bez oznacznika

  • Alt+C - dodaj pusty fragment kodu

Skróty operujące na kodzie i linijkach:

  • Alt+L - zaznaczenie całej linii
  • Alt+, Alt+ - przeniesienie linijki w której znajduje się kursor w górę/dół.
  • Tab/⌘+] - dodaj wcięcie (wcięcie w prawo)
  • Shit+Tab/⌘+[ - usunięcie wcięcia (wycięcie w lewo)

Dodawanie postów:

  • Ctrl+Enter - dodaj post
  • ⌘+Enter - dodaj post (MacOS)