Ευρεση αριθμού σε πινάκα

[hestia]

ειναι λιγο αδικο επειδη ασχολουμαι χρονια με νουμερα και αλγοριθμους πανω στα Νουμερα αλλα επεδη μου αρεσε το εφτιαξα.

 

Φτιαχνω 2 Αθροσιματα ενα με ολα τα Νουμερα που εχει ο πινακας

και ενα αθρισμα αποτελουμ,ενο απο τα νουμερα με μια φορα

αμ σωσετε τον παρακατω κωδικα και τπον τρεξετε θα δειτε οτι βγαζει το 100 με ενα απλο Loop.

 

 

 

 

 

<%

dim mydic

Set mydic=Server.CreateObject("Scripting.Dictionary")

 

'////////////Λουπα  ολα τα Νουμερα του πινακα μια φορα.

'/εστω Total_Num τα Στοιχεια του πινακα

'/εστω Mytable ο πινακας

dim mytable(6)

mytable(0)=1

mytable(1)=2

mytable(2)=100

mytable(3)=1

mytable(4)=3

mytable(5)=2

mytable(6)=3

 

 

full_sum=0

total_sum=0

 

for x=0 to ubound(mytable)

full_sum=full_sum+Mytable(x)

'Edo perno ta numera APO MIA FORA kai ftiaxno atrisma

if not mydic.Exists("a-" & Mytable(x))  then  

mydic.add "a-" & Mytable(x),Mytable(x)

total_sum=total_sum+Mytable(x)

end if

next

 

 

 

'////////////αφου τελιώσει η λοοπα 

'στην μεταβλητη full_sum εχω το Αθροισμα ολων των στοιχείων. πχ 200

'στην μεταβλητη  εχω το αθρισμα των μοναδικών πχ 100 

' Αν Ολα ηταν απο 2 φορες θα επρεπε να εχω αθρισμα  total_sum x 2 δηλαδη 106 χ 2 δηλαδη 212

' Αφου ομως εχω αθροισμα 112 σημαινει μου λειπουν 212-112 = 100 

' Αρα το 100 ειναι το Νουμερο που παιζει μονο μια φορα.

 

response.write "Unique Number  = " &  Abs(full_sum  - (total_sum*2)) 

 

 

'by mel

%>

 

 

[Aztec]

Κατσε περιμενε το mydic.exists τι κανει ελεγχει να δει αν υπαρχει ο αριθμος στο dictionary και αν οχι τον προσθετει ? τι πολυπλοκοτητα εχει αυτο ? Δεν προσθετει δηλαδη στο ηδη O(n) ?

[hestia]

Κατσε περιμενε το mydic.exists τι κανει ελεγχει να δει αν υπαρχει ο αριθμος στο dictionary και αν οχι τον προσθετει ? τι πολυπλοκοτητα εχει αυτο ? Δεν προσθετει δηλαδη στο ηδη O(n) ?

 

το mydic.exists βασταει στην μνημη τους αριθμους απο μια φορα που την ειδες την πουπλοκοτητα? 5 γραμμες κωδικας ειναι.

 

απλα εδωσα μια λυση στο συγκεκριμενο προβλημα.

[Aztec]

Α νομιζα οτι το complexity ειναι n(n+1)/2 αν το lookup θελει O(n)

 

Αν το lookup ειναι Ο(1) παω πασο

[Apoll]

Έχουμε ένα πινάκα με Ν αριθμούς όπου όλοι οι αριθμοί υπάρχουν 2 φορές εκτός από έναν.

πχ. { 1, 2, 100, 1, 3, 2, 3}

 

Βρείτε τον μοναδικό αριθμό με τον ποιο γρήγορο τρόπο.

 

*Δεν είναι εργασία.

 

Σε .ΝΕΤ 3.5+ με LINQ γίνεται εύκολα και χωρίς LINQ με Hash table σε 1.1 και Dictionary από 3.0