Author |
Topic: puzzle: find first non repeated character (Read 2899 times) |
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender: 
Posts: 319
|
 |
puzzle: find first non repeated character
« on: Dec 9th, 2004, 5:48pm » |
 Quote  Modify
|
Given an array of characters in array find first non-repeated character. ex. in "total" is 'o'
|
|
 IP Logged |
While we are postponing, life speeds by
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: puzzle: find first non repeated character
« Reply #1 on: Dec 10th, 2004, 5:57am » |
Quote Modify
|
Create an array of flags, one per character, set them to false.
Scan the string from the end. For each character: if the flag is false save the character and set the flag to true.
When done, the last saved character is the first non-repeated.
Advantage: for large strings, it is still O(n).
Problem: for short strings and large character sets, you still have to initialize the whole array of flags.
|
|
IP Logged |
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: puzzle: find first non repeated character
« Reply #2 on: Dec 10th, 2004, 9:34am » |
Quote Modify
|
where are you going to save the characters? create another array?
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: puzzle: find first non repeated character
« Reply #3 on: Dec 14th, 2004, 3:35am » |
Quote Modify
|
yes. If the character set is fixed, it is O(1).
|
|
IP Logged |
|
|
|
Margit
Guest
|
|
Re: puzzle: find first non repeated character
« Reply #4 on: Dec 16th, 2004, 12:47am » |
Quote Modify
 Remove
|
How does that work with eg. "AAB" ?
|
|
IP Logged |
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: puzzle: find first non repeated character
« Reply #5 on: Dec 16th, 2004, 2:14pm » |
Quote Modify
|
Hi I just wrote the alg based on your psuedo code, but it doesnt work:
#include<iostream>
using namespace std;
int main()
{
bool charFlag[26];
char chars[26], *in="total";
int last=-1;
for(int i=0;i<26;charFlag[i]=false,i++); // clear the flag arr
for(int i=0;i<=sizeof(in);i++)
{
if(charFlag[in[i]-'a']==true)
continue;
charFlag[in[i]-'a']=true;
chars[++last]=in[i];
}
cout<<chars[last]<<endl;
system("PAUSE");
return 0;
}
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: puzzle: find first non repeated character
« Reply #6 on: Dec 16th, 2004, 2:17pm » |
Quote Modify
|
Hi I just wrote the alg based on your psuedo code, but it doesnt work: (playing with code funcs  )
Code:
#include<iostream>
using namespace std;
int main()
{
bool charFlag[26];
char chars[26], *in="total";
int last=-1;
for(int i=0;i<26;charFlag[i]=false,i++); // clear the flag arr
for(int i=0;i<=sizeof(in);i++)
{
if(charFlag[in[i]-'a']==true)
continue;
charFlag[in[i]-'a']=true;
chars[++last]=in[i];
}
cout<<chars[last]<<endl;
system("PAUSE");
return 0;
} |
|
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: puzzle: find first non repeated character
« Reply #7 on: Dec 16th, 2004, 2:35pm » |
Quote Modify
|
I think you missed the 'from the end' part.
Start at the end of the string, and scan to the front.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: puzzle: find first non repeated character
« Reply #8 on: Dec 16th, 2004, 3:24pm » |
Quote Modify
|
Sorry, forgot to traverse in reverse... the problem is actually valid of aab... it iwll report a is a last stored char.....
Code:i
#nclude<iostream>
using namespace std;
int main()
{
bool charFlag[26];
char chars[26], *in="aab";
int last=-1;
for(int i=0;i<26;charFlag[i]=false,i++); // clear the flag arr
for(int i=sizeof(in)+1;i>=0;i--)
{
if(charFlag[in[i]-'a'])
continue;
charFlag[in[i]-'a']=true;
last =i;
}
cout<<in[last]<<endl;
system("PAUSE");
return 0;
}
|
|
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
puzzlecracker
Senior Riddler
Men have become the tools of their tools
Gender:
Posts: 319
|
|
Re: puzzle: find first non repeated character
« Reply #9 on: Dec 16th, 2004, 5:45pm » |
Quote Modify
|
oK sorry for the bombardment: here is the correct solution to the problem
create a hashtable for each char,
zero out every element
for every occurance of the character, increment the coutner
go through string array again and if that char hashes to 1, return it.
i implemented hash using array
Code:
#include<iostream>
using namespace std;
int main()
{
int charFlag[26];
char *in="aab";
for(int i=0;i<26;charFlag[i]=0,i++); // clear the flag arr
for(int i=0;i<=sizeof(in);++i)
charFlag[in[i]-'a']++;
for(int i=0;i<=sizeof(in);++i)
if(charFlag[in[i]-'a']==1){
cout<<in[i]<<endl;
break;
}
system("PAUSE");
return 0;
}
|
|
|
|
IP Logged |
While we are postponing, life speeds by
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print