Πρώτος μοναδικός χαρακτήρας σε ένα String

[Asevastos]

Καλησπέρα,

έχω ένα πρόβλημα το οποίο κοιτάω εδώ και αρκετή ώρα και δυσκολεύομαι να βρω που κάνω λάθος(ίσως να φταίει και η ώρα).

Δίνεται ένα string, πρέπει να βρω τον πρώτο χαρακτήρα που δεν επαναλαμβάνεται και να επιστρέψω το index του.

Τι σκέφτηκα:

Είπα ωραία, θα πάρω το String, θα το περάσω σε ένα πίνακα χαρακτήρων για να μπορώ να χειρίζομαι τους δείκτες των χαρακτήρων βολικά. Δημιουργώ το array χαρακτήρων και σκέφτηκα το εξής. Τώρα, θα παίρνω έναν έναν τους χαρακτήρες, θα τους μεταφέρω στην αρχή του πίνακα με το όνομα key(αντιμετάθεση με το 1ο στοιχείο) και θα συγκρίνω το key με όλους τους υπόλοιπους χαρακτήρες. Κάθε φορά που το key είναι διαφορετικό από κάποιο χαρακτήρα, θα αυξάνω έναν μετρητή. Εάν στο τέλος αυτός ο μετρητής έχει τιμή ίση με το μέγεθος του πίνακα πλην ένα(που σημαίνει ότι για όλους τους υπόλοιπους χαρακτήρες εκτός του ίδιου του key ο μετρητής αυξήθηκε), σημαίνει ότι το στοιχείο είναι το πρώτο μοναδικό και άρα επιστρέφω τον δείκτη του. Άμα δεν υπάρχει τέτοιο στοιχείο, επιστρέφει -1.

Ο κώδικας:

class Solution {
    public int firstUniqChar(String s) {
        Character[] ch = new Character[s.length()];
        for (int i=0;i<s.length();i++){
            ch[i] = s.charAt(i);
        }
        for (int i=0;i<s.length();i++){
            char key = ch[i];
            int count = 0;
            char temp = ch[0];
            ch[0] = key;
            key = temp;
            for (int j=1;j<s.length();j++){
                if (key!=ch[j]) count++;
            }
            if (count==s.length()-1) return i;
        }
        return -1;
    }
}

 

Επεξ/σία 17 Νοεμβρίου 2018 από Asevastos

[defacer]

Δεν κάνεις κάποια συγκεκριμένη ερώτηση όμως.

Γενικά μιλώντας:

Γιατί μπαίνεις στον κόπο να μεταθέσεις το λεγόμενο key στην πρώτη θέση; Και εκεί που είναι να το αφήσεις ακριβώς ο ίδιος αλγόριθμος θα δώσει ακριβώς το ίδιο αποτέλεσμα.

Γιατί κουράζεσαι να μετράς μέχρι το τέλος και να βλέπεις αν έφτασε ο μετρητής στο n - 1? Δε χρειάζεται κανένας μετρητής. Αν βρεις τον ίδιο χαρακτήρα σε άλλη θέση εκτός του τρέχοντος index, δεν είναι μοναδικός, πάμε στο επόμενο index. Ούτε μετρητές ούτε τίποτα. Επίσης αυτό είναι και πιο γρήγορο, γιατί δεν κάθεσαι να μετρήσεις ακριβώς πόσες φορές εμφανίζεται, δε σε νοιάζει. Σε νοιάζει μόνο αν εμφανίζεται πάνω από μια.

Επεξ/σία 17 Νοεμβρίου 2018 από defacer

[antbyron]

Δεν έχω καταλάβει ακριβώς τι θέλεις να κάνεις, αλλά νομίζω το έχεις περιπλέξει λίγο. Τι θα έκανα, θα ξεκινούσα από τον πρώτο χαρακτήρα και θα τον σύγκρινα με τους επόμενους, αν έβρισκα duplicates θα τους σημάδευα για να μην τους ξαναελέγξω και θα συνέχιζα με τους επόμενους, αν δεν έβρισκα duplicates τότε βρήκα την λύση και θα κρατούσα το index. Δεν νομίζω ότι χρειάζεται να κάνεις αντιμεταθέσεις κλπ.

[kaliakman]

Όντως το έχεις περιπλέξει λίγο. Μια O(n) λύση που σκέφτηκα είναι:

1) Έχεις έναν πίνακα 26 θέσεων(δεδομένου ότι μιλάμε για αγγλικά αλλιώς το αλλάζεις) για αποθήκευση συχνότητας

2) Περνάς το string και σημειώνεις την συχνότητα του κάθε γράμματος.

3) Περνάς ξανά το string και το πρώτο γράμμα με frequency 1 είναι το αποτέλεσμα σου.

Επεξ/σία 17 Νοεμβρίου 2018 από kaliakman

[Asevastos]

Καλημέρα παιδιά και ευχαριστώ για τις απαντήσεις. Defacer η ερώτηση ήταν γιατί δε μου έβγαζε σωστά αποτελέσματα.  Όντως το είχα περιπλέξει παραπάνω από όσο έπρεπε, απλώς είχα κολλήσει επειδή δε μου έβγαινε σωστό και δεν έψαχνα άλλες λύσεις, απλώς ήθελα να βρω γιατί δε γίνεται. Με πιο καθαρό μυαλό σήμερα, παραθέτω τη παρακάτω, πιο σύντομη λύση που είναι και σωστή(χωρίς counter και ιστορίες όπως σωστά μου επισημάνατε):

class Solution {
    public int firstUniqChar(String s) {
        Character[] ch = new Character[s.length()];
        for (int i=0;i<s.length();i++){
            ch[i] = s.charAt(i);
        }
        for (int i=0;i<s.length();i++){
            boolean bool = true;
            char key = ch[i];
            for (int j=0;j<s.length();j++){
                if (key==ch[j] && i!=j){
                    bool = false;
                    break;
                }
            }
            if (bool) return i;
        }
        return -1;
    }
}

Ευχαριστώ για τις συμβουλές. 

Επεξ/σία 17 Νοεμβρίου 2018 από Asevastos

[masteripper]

Θα μπορούσες να διατρέχεις το string  και σε κάθε χαρακτήρα να κάνεις replace με το null....στον 1ο χαρακτήρα που το μήκος του τελικου string είναι ίσο με το μήκος του αρχικού-1 είναι και ο ζητούμενος...

[marios28]

Στη δεύτερη for, αντί για j=0, νομίζω μπορείς να το αλλάξεις σε j=i+1 (το προηγούμενο γράμμα έχει ήδη συγκριθεί με τα επόμενα, οπότε δε χρειάζεται να ξανακάνουμε την ίδια σύγκριση για το επόμενο με τα προηγούμενα). Οπότε μπορείς από τη σύγκριση παρακάτω να βγάλεις το  && i!= j.

Επεξ/σία 17 Νοεμβρίου 2018 από marios28

[Asevastos]

Ναι, ισχύει ότι μπορώ να το βγάλω. Θα προχωρήσω σε άλλα προβλήματα τώρα και το βραδάκι θα κάτσω μάλλον να βελτιώσω τον αλγόριθμο και να τον κάνω καλύτερο από quadratic  

Επεξ/σία 17 Νοεμβρίου 2018 από Asevastos

[albNik]

10 ώρες πριν, kaliakman είπε

Όντως το έχεις περιπλέξει λίγο. Μια O(n) λύση που σκέφτηκα είναι:

1) Έχεις έναν πίνακα 26 θέσεων(δεδομένου ότι μιλάμε για αγγλικά αλλιώς το αλλάζεις) για αποθήκευση συχνότητας

2) Περνάς το string και σημειώνεις την συχνότητα του κάθε γράμματος.

3) Περνάς ξανά το string και το πρώτο γράμμα με frequency 1 είναι το αποτέλεσμα σου.

Στον πίνακα αποθηκεύεις την θέση που βρήκες τον κάθε χαρακτήρα. Στο α[0] τη θεση του Α, α[1] τη θέση του Β...

Αρχικα ολες οι θεσεις να ειναι -2.

Αν υπαρχει ηδη η θεση με α[x] >=0 σημαίνει οτι επαναλαμβανεται και βαλε ακυρο  π.χ .-1, και αγνοησε οσες φορες δεις -1.

Eπιστρεφεις το α[x] με μικρότερο νουμερο >=0.

Δλδ

αν α[3]=-2 :δεν υπάρχει το γραμμα D

α[3]=-1  : επαναλαμβανεται το γραμμα D

α[3]= 5 : το γραμμα D υπαρχει μονο μια φορα στην εκτη θεση

θες μονο ενα περασμα στο string  O(n+26)

Επεξ/σία 17 Νοεμβρίου 2018 από albNik

[defacer]

50 minutes ago, marios28 said:

Στη δεύτερη for, αντί για j=0, νομίζω μπορείς να το αλλάξεις σε j=i+1 (το προηγούμενο γράμμα έχει ήδη συγκριθεί με τα επόμενα, οπότε δε χρειάζεται να ξανακάνουμε την ίδια σύγκριση για το επόμενο με τα προηγούμενα). Οπότε μπορείς από τη σύγκριση παρακάτω να βγάλεις το  && i!= j.

Δεν ισχύει αυτό. Έχεις το string XX. Εξετάζεις το πρώτο Χ, κοιτάς παρακάτω, βλέπεις ότι ξαναεμφανίζεται, λες οκ πάμε παρακάτω.

Θες να εξετάσεις λοιπόν το δεύτερο Χ. Now what?

10 hours ago, kaliakman said:

1) Έχεις έναν πίνακα 26 θέσεων(δεδομένου ότι μιλάμε για αγγλικά αλλιώς το αλλάζεις) για αποθήκευση συχνότητας

Σε καμία απολύτως περίπτωση δεν είναι ικανοποιητική λύση άσκησης αυτή που υποθέτει 26 χαρακτήρες εκτός αν δίνεται ρητά σα δεδομένο.

Στη γενική περίπτωση οι χαρακτήρες είναι αρκετοί για να μην προσφέρει τίποτα η λύση πίνακα (hash table όμως άλλη υπόθεση).

Επεξ/σία 17 Νοεμβρίου 2018 από defacer

[kaliakman]

19 λεπτά πριν, defacer είπε

Δεν ισχύει αυτό. Έχεις το string XX. Εξετάζεις το πρώτο Χ, κοιτάς παρακάτω, βλέπεις ότι ξαναεμφανίζεται, λες οκ πάμε παρακάτω.

Θες να εξετάσεις λοιπόν το δεύτερο Χ. Now what?

Σε καμία απολύτως περίπτωση δεν είναι ικανοποιητική λύση άσκησης αυτή που υποθέτει 26 χαρακτήρες εκτός αν δίνεται ρητά σα δεδομένο.

Στη γενική περίπτωση οι χαρακτήρες είναι αρκετοί για να μην προσφέρει τίποτα η λύση πίνακα (hash table όμως άλλη υπόθεση).

Στο context της άσκησης αναφέρεται τι input έχει. Προφανώς μπορεί να πάει στο μέγεθος ascii ή και αν αυτό δεν είναι πάλι αρκετό όπως σωστά είπες πάει σε hash table. 

Η πιο γενική λύση συμφωνώ πως είναι το hash table πάντως. 

[marios28]

29 λεπτά πριν, defacer είπε

Δεν ισχύει αυτό. Έχεις το string XX. Εξετάζεις το πρώτο Χ, κοιτάς παρακάτω, βλέπεις ότι ξαναεμφανίζεται, λες οκ πάμε παρακάτω.

Θες να εξετάσεις λοιπόν το δεύτερο Χ. Now what?

Έχεις δίκιο. Πρέπει από την αρχή να γίνει η επανάληψη στην παραπάνω λύση.

 

7 λεπτά πριν, kaliakman είπε

Η πιο γενική λύση συμφωνώ πως είναι το hash table πάντως. 

Και 'γω το ίδιο. Κάτι τέτοιο όπως παρακάτω θα επέλεγα. Ενώ στην if στη δεύτερη περίπτωση μπορούν να εξεταστούν διάφορες περιπτώσεις (ανάλογα με τη συχνότητα εμφάνισης).

        String name = "fdsfasfsaffa";        

        HashMap<Character, Integer> hashmap = new HashMap<>();
        for (int i = 0; i < name.length(); ++i)
        {
            Character ch = name.charAt(i);
            if(hashmap.containsKey(ch))
            {
               Integer value = hashmap.get(ch);
               hashmap.replace(ch, ++value);
            }
            else
               hashmap.put(name.charAt(i), 1);
        }
      
        for (int i=0; i < name.length(); ++i)
        {
            Character ch = name.charAt(i);
            if(hashmap.get(ch) == 1)
            {
                System.out.println(ch + ": " + i);
                break;
            }
        }

 

[k33theod]

Ίσως να λέω το ίδιο πράγμα σαν αυτό με το hash:

Κάνεις στο string ένα πέρασμα και μετράς πόσες φορές επαναλαμβάνεται ο κάθε χαρακτήρας.  Αυτό σε python γίνεται έτσι

metritis={}
for i in str:
	if i in metritis:
		metritis[i]+=1
	else: metritis[i]=1

Mετά θα βρεις σε πιο index αντιστοιχεί το πρώτο στοιχείο του metritis που έχει τιμή 1

 

for i in metritis:
	if metritis[i]==1:
		return str.index(i)
return -1

Αυτά με την προυπόθεση ότι η γλώσσα δεν έχει κάποιο έτοιμο counter που μετράεις τις επαναλήψεις στα iterables. Αν έχει και η java αντίστοιχο με τον Counter της python ο κώδικας απλουστεύται μόνο στο 2ο μίσο.

Απ ότι βλέπω ο marios28 κάνει το ίδιο μόνο που στο δεύτερο iteration είναι νομίζω προτιμότερο να διαβάσει το hashmap και όχι το string

Επεξ/σία 17 Νοεμβρίου 2018 από k33theod
Marios28

[pmav99]

@k33theod

Το snippet που έδωσες δεν θα τρέχει σωστά σε Python < 3.7 γιατί το ordering των dictionary keys είναι διαφορετικό από το insertion order. Για την ακρίβεια θα τρέχει και σε CPython 3.6 αλλά όχι σε άλλα implementations όπως το PyPy (source). Κατά συνέπεια το "for i in metritis" μόνο από τύχη θα σου βρει το πρώτο γράμμα που είναι και το ζητούμενο. Σε python 3.7 θα τρέξει φυσικά ΟΚ, αλλά επειδή ο κώδικας σου δεν ξέρεις που θα τρέξει καλό είναι να το έχεις υπόψη σου και να μην εξαρτάσαι (ακόμα) από αυτό το feature.

Από εκεί και πέρα, πέρα από το Counter που είναι η σωστή λύση για το συγκεκριμένο πρόβλημα, ο ιδιωματικός τρόπος να γράψεις το πρώτο loop είναι με defaultdict το οποίο σου επιτρέπει να αποφύγεις το if μέσα στο loop.

from collections import defaultdict

frequencies = defaultdict(int)
for c in my_string:
    frequencies[c] += 1

Για να καταλάβεις τι ακριβώς κάνει, δες αυτό και αυτό:

from collections import defaultdict

aaa = defaultdict(int)
aaa["a"] += 1
aaa["a"] += 3
print(aaa)
counter["b"]
print(aaa)

 

Επεξ/σία 17 Νοεμβρίου 2018 από pmav99

[solarpower]

Φτιάχνουμε ένα πίνακα ίσο με το μήκος του αλφαριθμητικού, boolean.

θα χρειαστούμε μια f ως boolean

ξεκινάμε με p=1 και i=2. βάζουμε σε μια μεταβλητή τον πρώτο χαρακτήρα, έστω στην c

χρησιμοποιούμε μια ΟΣΟ p<i και ι<μήκος αλφαριθμητικου

Κάθε φορά ελέγχουμε το πίνακα αν στο ι είναι αληθής, αν είναι τότε περνάμε τον έλεγχο του στοιχείου στη i θέση του αλφαριμθητικού. Άν βρούμε ίσο τότε βάζουμε στην αντίστοιχη θέση των boolean αληθές και ενημερώνουμε και μια μεταβλητή  f (flag)  ως αληθής

αυξάνουμε το ι

ελέγχουμε αν το ι είναι μεγαλύτερο ή ίσο από το μήκος του αλφαριθμητικού (μπορούμε να το έχουμε σε μεταβλητή και αν το f είναι αληθής (σημαίνει ότι τελειώσαμε τον έλεγχο για ένα στοιχείο και υπήρχε τουλάχιστον ένα ίδιο).

Αν πράγματι η συνθήκη ικανοποιείται τότε αυξάνουμε το p και κοιτάμε από το πίνακα των boolean αν αντίστοιχη θέση είναι αληθής, αν είναι τότε αυξάνουμε το p (σε μια όσο p<n). Σημασία έχει εδώ να βγούμε με ένα p για νέο χαρακτήρα,  Βάζουμε το χαρακτήρα στο c και θέτουμε το i<-p+1 και το f ως ψευδές (ώστε να το μαρκάρουμε στο επόμενο διπλό).

Αφού βγούμε από την όσο, αν η f είναι ψευδής τότε στο c έχουμε τον μοναδικό πρώτο χαρακτήρα.

 

 

Επεξ/σία 18 Νοεμβρίου 2018 από solarpower