Hallo,
ich versuche mich gerade an einer Aufgabe auf codefights.com. Die
Aufgabe möchte ich in C lösen
Die Aufgabe ist wie folgt:
Given an array a that contains only numbers in the range from 1 to
a.length, find the first duplicate number for which the second
occurrence has the minimal index. In other words, if there are more than
1 duplicated numbers, return the number for which the second occurrence
has a smaller index than the second occurrence of the other number does.
If there are no such elements, return -1.
Example
For a = [2, 3, 3, 1, 5, 2], the output should be
firstDuplicate(a) = 3.
There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has
a smaller index than than second occurrence of 2 does, so the answer is
3.
For a = [2, 4, 3, 5, 1], the output should be
firstDuplicate(a) = -1.
Input/Output
[execution time limit] 0.5 seconds (c)
[input] array.integer a
Guaranteed constraints:
1 ≤ a.length ≤ 105,
1 ≤ a[i] ≤ a.length.
The element in a that occurs in the array more than once and has the
minimal index for its second occurrence. If there are no such elements,
return -1.
1
// Definition for arrays:
2
// typedef struct arr_##name {
3
// int size;
4
// type *arr;
5
// } arr_##name;
6
//
7
// arr_##name alloc_arr_##name(int len) {
8
// arr_##name a = {len, len > 0 ? malloc(sizeof(type) * len) : NULL};
Der Code funktioniert auch. Allerdings bekomme ich für einen Test die
Fehlermeldung, dass mein Code zu langsam ist.
Gibt es eine Methode, mit der ich direkt doppelte Einträge abfragen
kann? Also dass ich nicht mit for-Schleifen den array durchgehen muss?
habe schon versucht den Code schneller zu machen
a.size = y; -> Die For-Schleife wird verkürzt, sodass nicht mehr alles
durchgegangen werden muss
if((y-x)==1) return value; -> einen ängeren abstand als 1 gibt es nicht,
von daher kann hier sofort alles abgebrochen werden
break; -> der rest der for-Schleife muss nicht mehr durchgegangen
werden, da das pärchen mit diesem Wert schon gefunden wurde
Gruß
Johannes
Johannes schrieb:> Given an array a that contains only numbers in the range from 1 to> a.length,
Der Extremwert für's Maximum ist doch bekannt ?!?
Hilfsarray erstellen mit [0-a.length]
Dein Original absuchen und im Hilfsarray markieren ob der Wert schon
vorgekommen ist oder nicht.
Thomas G. schrieb:> Johannes schrieb:>> Given an array a that contains only numbers in the range from 1 to>> a.length,>> Der Extremwert für's Maximum ist doch bekannt ?!?> Hilfsarray erstellen mit [0-a.length]>> Dein Original absuchen und im Hilfsarray markieren ob der Wert schon> vorgekommen ist oder nicht.
In der Originalaufgabe steht meist noch Laufzeit O(n) und zusätzlicher
Speicher O(1) ;) Also Inplace statt extra Speicher.
Hi,
Zuerst sowas durch arbeiten und dann anfangen solche 'challanges' zu
bearbeiten kann weniger frustrierend sein:
http://ls2-www.cs.tu-dortmund.de/grav/grav_files/lehre/sommer2007/dap2/skript.pdf
Das Problem ist Dein Algorithmus hat eine Komplexität von O(n²). Das
geht auch in O(n Log(n)): sortieren mit z.B. quick sort und beim
Vergleich bei Gleichheit abbrechen. Da der Input random ist, sollte das
optimal sein, wenn der Input umgekehrt sortiert sein kann, würde ich
über bottom-up heapsort nehmen und mir den kleinsten Input Index merken
der gleich war.
Grüße
Thorsten
Arc N. schrieb:> In der Originalaufgabe steht meist noch Laufzeit O(n) und zusätzlicher> Speicher O(1) ;) Also Inplace statt extra Speicher.
in dem fall:
das oberste bit des ints in dem array könnte man als "schonmal gesehen"
bit deklarieren. solange das array kleiner als 2,xx Mrd einträeg hat
(und 32bit ist) sollte es da kein problem geben.
Und die Definition von Duplikat heißt, dass das erste gefundene Pärchen
das gesuchte ist.
Das gane lässt sich also in O(n) lösen, sofern man n bits speicher an;
sprich:
1
for(i=0;i<len;++i){
2
intv=a[i]&0x7fFFffFF;
3
boolseen=a[v]&0x80000000;
4
if(seen){
5
break;// gefunden
6
}
7
a[v]=a[v]|0x80000000;
8
}
Falls a readonly ist, dann eben doch ein separates Bitset anlegen.
Speicherbedarf also n/8 Bytes
was hälst du davon? von vorne durch gehen, ob es die zahl schon mal gab.
Erstes Dublikat ist das Ergebnis.
Gruß Scyte
p.s. das von Vlad Tepesch geht natürlich auch, da int minimum 16bit ist
und das größte Element wäre 105 nach Aufgabenstellung.
Scyte R. schrieb:> p.s. das von Vlad Tepesch geht natürlich auch, da int minimum 16bit ist> und das größte Element wäre 105 nach Aufgabenstellung.
oh, das hab ich ganz übersehen.
Das ist ja lächerlich. Wie wollen sie da messen, ob man da O(n) oder
O(n³) code produziert?
Arc N. schrieb:> Thomas G. schrieb:>> Der Extremwert für's Maximum ist doch bekannt ?!?>> Hilfsarray erstellen mit [0-a.length]>>>> Dein Original absuchen und im Hilfsarray markieren ob der Wert schon>> vorgekommen ist oder nicht.>> In der Originalaufgabe steht meist noch Laufzeit O(n) und zusätzlicher> Speicher O(1) ;) Also Inplace statt extra Speicher.
Passt doch. a.length ist nach oben durch 150 beschränkt, d.h. ein
zusätzliches Array mit a.length Elementen verbraucht zusätzlichen
Speicher O(1) da durch eine Konstante unabhängig von der Eingabe nach
oben abschätzbar.
Johannes schrieb:> habe schon versucht den Code schneller zu machen
Mit zusätzlichen O(n) Speicher hat Thomas bereits die Lösung gezeigt mit
einer Laufzeit O(n). (Von anderen Postern sind es lediglich Varianten
davon.)
Die In-Place Lösung von Scyte ist besser als deine; falls es denn ein
Duplikat gibt. Die Komplexität ist aber mit O(n²) genauso hoch.
Eine In-Place Lösung, die die numerischen* Vorgaben ausnutzen könnte,
sehe ich auf Anhieb nicht (*also bspw. unter Ausnutzung vom
Restklassen).
Eine generische In-Place Lösung könnte iterativ die ersten m Elemente
sortiert vorhalten, und das Element an (m+1) über Binärsuche prüfen /
einfügen. Einfügen In-Place geht jedoch nicht in O(ld(m)). Daher wird
man wohl mit sortierten Chunks arbeiten müssen und die "optimale"
Komplexität O(n * ld(n)) nicht ganz erreichen.
Das oben vorgeschlagene Sortieren / Auffinden von Duplikaten in
O(n*ld(n)) funktioniert hier nicht, da dabei die Position der Elemente
verloren geht. Die Position wird aber als Rückgabewert benötigt.
Arc N. schrieb:> In der Originalaufgabe steht meist noch Laufzeit O(n) und zusätzlicher> Speicher O(1)
Öhm, nö, steht bei ihm nicht.
Und wenn er zu faul ist, die ganze Aufgabe abzuschrieben weil er meint
das wäre egal - dann ist das sein Problem.
> Arc N. schrieb:>> In der Originalaufgabe steht meist noch Laufzeit O(n) und zusätzlicher>> Speicher O(1)>> Öhm, nö, steht bei ihm nicht.>> Und wenn er zu faul ist, die ganze Aufgabe abzuschrieben weil er meint> das wäre egal - dann ist das sein Problem.
Wenn das weggelassen wird, kann sich an Bucketsort/Countingsort
angelehnt werden...
1
intfirstDuplicate(arr_integera){
2
intpos[MAX_ARRAY_SIZE+1]={0};
3
intminIndex=INT_MAX;
4
for(inti=1;i<a.size+1;i++){
5
intvalue=a.arr[i-1];
6
if(pos[value]==0){
7
// never seen before
8
pos[value]=-i;
9
}else{
10
if(pos[value]<0){
11
// occured once before
12
pos[value]=i;
13
// optimization:
14
returni;// must be the lowest index so we can terminate here
15
16
}else{
17
// occured more than twice before
18
// optimization: don't care, since this can't be the lowest index
19
pos[value]=min(pos[value],i);
20
}
21
minIndex=min(pos[value],minIndex);
22
}
23
}
24
return(minIndex==INT_MAX)?-1:minIndex;
25
}
Ausgehend davon, kann jetzt das pos-Array weggelassen werden...
Arc N. schrieb:> Wenn das weggelassen wird
...dann wurde bereits in der ersten Antwort die Lösung beschrieben und
danach mehrfach wiederholt.
Wer hat eine In-Place Lösung die besser als O(n²) ist; ohne zusätzlichen
Speicher und ohne Modifikation der Elemente ausserhalb ihres
Wertebereichs: 1 ≤ a[i] ≤ a.length?
Mikro 7. schrieb:> Wer hat eine In-Place Lösung die besser als O(n²) ist; ohne zusätzlichen> Speicher und ohne Modifikation der Elemente ausserhalb ihres> Wertebereichs: 1 ≤ a[i] ≤ a.length?
Die hab ich doch gepostet.
Achso - ohne Modifikation außerhalb ihres wb
Das heißt aber, dass du keine zusätzlichen Informationen anlegen kannst.
Und bei 105 bietet ja so ein Byte noch ein freies Bit
Johann L. schrieb:> e statt extra Speicher.>> Passt doch. a.length ist nach oben durch 150 beschränkt, d.h. ein> zusätzliches Array mit a.length Elementen verbraucht zusätzlichen> Speicher O(1) da durch eine Konstante unabhängig von der Eingabe nach> oben abschätzbar.
Machs doch einfach wie bereits beschrieben, zuerst sortieren, dann
durchiterieren.
std::sort wäre meine Wahl in C++, quicksort kann problematisch sein beim
worst case. Wenn du aber nur ein paar Hundert Elemente hast, dann ist
das egal.
https://www.geeksforgeeks.org/c-qsort-vs-c-sort/
Man darf übrigens nicht vernachlässigen, dass die Sprungvorhersage bei
einem sortierten Array für eine relativ flotte Ausführung sorgt, da
müsste man sich die Lösung von Vlad Tepesch mal im Vergleich bei
entsprechend großen Datenmengen anschauen.
Egon N. schrieb:> Machs doch einfach wie bereits beschrieben, zuerst sortieren, dann> durchiterieren.
Und wie findest du dann den Wert des ersten Duplikats? Nach dem
Sortieren stehen die Wert an anderen Stellen und bei dem Beispiel wäre
dann die 2 die erste Doublette:
Johannes schrieb:> Example> For a = [2, 3, 3, 1, 5, 2], the output should be> firstDuplicate(a) = 3.
Johannes schrieb:> [execution time limit] 0.5 seconds (c)>> ...>> Guaranteed constraints:> 1 ≤ a.length ≤ 105,
Selbst der lausigste Algorithmus wird für die Bearbeitung der 105
Elemente nie 0,5 Sekunden benötigen. Selbst bei vollständigem paarweisen
Vergleich sind nur 102²=11025 Vergleiche erforderlich, was auch ein
relativ schwacher Prozessor locker in der Zeit schafft.
Woher kommt überhaupt die krumme Zahl 105? Wieso nimmt man nicht 100
oder 128? Wurde da vielleicht etwas falsch kopiert, und es sollte in
Wirklichkeit
1 ≤ a.length ≤ 10⁵
heißen?
Yalu X. schrieb:> Wurde da vielleicht etwas falsch kopiert, und es sollte in> Wirklichkeit>> 1 ≤ a.length ≤ 10⁵
Klingt plausibel.
Müsste man mal beim Original nachschauen, was wohl von codefights.com
kommt. Allerdings braucht man einen Account, um da rein sehen zu können.
Der Link wäre
https://codefights.com/interview-practice/task/pMvymcahZ8dY4g75q
Vlad T. schrieb:> Die hab ich doch gepostet.> Achso - ohne Modifikation außerhalb ihres wb
So ganz geht das aber ned. Oder ich hab deinen Code oder die Aufgabe
nicht richtig verstanden.
Array Größe 105 = a[0...104] Werte drinnen 1...105
int v = a[i] & 0x7fFFffFF;
bool seen = a[v] & 0x80000000;
Was passiert wenn a[i] = 105 ist... a[105] gibbet's ned.
Müßte doch dann ehr:
Edit:
int v = (a[i] -1) & 0x7fFFffFF;
Oder hab ich falsch gedacht?
Michael B. schrieb:> Die Werte drinnen könnten ja auch 0..104 sein.
Könnten sie, aber dürfen sie nicht:
Johannes schrieb:> Guaranteed constraints:> 1 ≤ a.length ≤ 105,> 1 ≤ a[i] ≤ a.length.
das klingt plausibel.
Yalu X. schrieb:> Und es sollte in> Wirklichkeit>> 1 ≤ a.length ≤ 10⁵>> heißen?
Damit wäre auch meine Frage von oben geklärt:
Vlad T. schrieb:> Wie wollen sie da messen, ob man da O(n) oder> O(n³) code produziert?Thomas G. schrieb:> So ganz geht das aber ned. Oder ich hab deinen Code oder die Aufgabe> nicht richtig verstanden.> Array Größe 105 = a[0...104] Werte drinnen 1...105
der code sollte eher das Prinzip verdeutlichen.
Johannes schrieb:> Guaranteed constraints:> 1 ≤ a.length ≤ 105,> 1 ≤ a[i] ≤ a.length.
da null nicht erlaubt ist, kann man alles um eins schieben, dann passt
es.
ansonsten könnte man auch noch die obersten 2 bits benutzen, wenn man
sicherstellt, dass sie nicht gebraucht werden.
Egon N. schrieb:> Machs doch einfach wie bereits beschrieben, zuerst sortieren, dann> durchiterieren.>> std::sort wäre meine Wahl in C++, quicksort kann problematisch sein beim> worst case. Wenn du aber nur ein paar Hundert Elemente hast, dann ist> das egal.
ne, sortieren geht nicht, dann sind ja die positionen verloren.
Und dann bist du bei der Rechenzeit mindestens bei O(n log n), anstelle
bei O(n).
Wenn du die alten Indices behalten wills, musst du ne Tabelle mit den
alten Indices beim sortieren mitpflegen, das heißt du brauchst auf jeden
Fall mehr zusätzlichen Speicher, als die N/8 Bytes für den
Lookup-Bitvektor
Stefan A. schrieb:> habe mich grad mal angemeldet bei dieser Seite. Es sind 10^5>> und es ist die erste Aufgabe, die man Freischalten muss..
Okay, also zu groß für 16bit und bei 32 sind genug bis frei, dass man da
noch ne Menge reinpacken kann ;-)
Vlad T. schrieb:> ne, sortieren geht nicht, dann sind ja die positionen verloren.>> Und dann bist du bei der Rechenzeit mindestens bei O(n log n), anstelle> bei O(n).> Wenn du die alten Indices behalten wills, musst du ne Tabelle mit den> alten Indices beim sortieren mitpflegen, das heißt du brauchst auf jeden> Fall mehr zusätzlichen Speicher, als die N/8 Bytes für den> Lookup-Bitvektor
O(n) und ohne weiteren Speicher geht nunmal nicht. Einen Tod wirst du
sterben müssen.
Egon N. schrieb:> geht nunmal nicht
Nun ja, die Aufgabe ist ja sehr speziell formuliert -- wenn alle Werte >
0 sind, kann man ja einfach die schon gefundenen Werte durch einen
negativen Wert markieren, etwa für 7 Zahlen nach
1
import random
2
3
proc main(): int =
4
const N = 7
5
var a = newSeq[int](N + 1) # N + 1 elements, we ignore position 0
6
for i in 0 .. a.high:
7
a[i] = i
8
a.shuffle
9
for i in 0 .. a.high: # put value 0 back at pos 0
10
if a[i] == 0:
11
swap(a[i], a[0])
12
break
13
a[5] = a[2] # create arbitrary duplicate
14
echo a[1 .. ^1]
15
for i in 1 .. a.high:
16
let v = a[i].abs
17
if a[v] < 0:
18
echo "Duplicate found at position ", i, '(', v, ')'
19
return i
20
else:
21
a[v] *= -1 # mark as already seen
22
echo "No duplicates found"
23
return -1
24
25
echo "return value is: ", main()
Ergibt dann
[code]
$ ./f
@[3, 2, 6, 1, 2, 4, 7]
Duplicate found at position 5(2)
return value is: 5
[\code]
Egon N. schrieb:> O(n) und ohne weiteren Speicher geht nunmal nicht. Einen Tod wirst du> sterben müssen.
der zusätzliche speicher ist ja schon da, da die Inputdaten weniger Bits
Informaionen beinhalten, als der der nächst größere Datentyp
bereistellt.
Stefan schrieb:> Ach, hatte Vlad ja eh schon geschrieben...
Deine Lösung, das entsprechende Feld zu negieren, find ich eleganter
(vorausgesetzt natürlich, der datentyp ist signed). ist nich soviel
bitgefummel und leicher lesbar
