この質問に答える次のプログラムを書きました
文字列内の最初の繰り返されない文字を見つける効率的な関数を作成します。たとえば、「total」の最初の繰り返しのない文字は「o」であり、「teeter」の最初の繰り返しのない文字は「r」です。アルゴリズムの効率について話し合います。
これは私がしたことです：
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
class Node
{
public:
Node::Node(char ch)
{
c = ch;
next = NULL;
}
char c;
Node *next;
};
Node* addNode(Node *tail, char ch)
{
if(tail == NULL)
return new Node(ch);
else
{
Node *newN = new Node(ch);
tail->next = newN;
return newN;
}
}
void deleteNode(char ch, Node** head, Node**tail)
{
Node *prev = NULL;
Node *cur = *head;
while(cur!=NULL)
{
if(cur->c == ch)
{
// found cut it
if(prev == NULL)
{
// head cut off
if(*tail == *head)
{
// worst possible, just one element
delete *head;
*head = NULL;
return;
}
else
{
// Head cut off but not just first element
Node *tmp = *head;
*head = (*head)->next;
delete tmp;
return;
}
}
else
{
// delete normal node
if(*tail == cur)
{
// delete tail
Node *tmp = *tail;
*tail = prev;
delete tmp;
return;
}
else
{
// Normal node not tail
prev->next = cur->next;
delete cur;
return;
}
}
}
// no match keep searching
prev = cur;
cur = cur->next;
}
}
int main()
{
char str[] = "total";
char htable[26];
memset(htable, 0, sizeof(char)*26);
Node *head = NULL;
Node *tail = head;
for(unsigned int i=0;;i++)
{
if(str[i] == '\0')
break;
// check first match
char m = htable[str[i]-'a'];
switch(m)
{
case 0:
{
// first time, add it to linked list
htable[str[i]-'a']++;
tail = addNode(tail, str[i]);
if(head == NULL)
head = tail;
}break;
case 1:
{
// bam, cut it out
htable[str[i]-'a']++;
deleteNode(str[i], &head, &tail);
}break;
}
}
if(head != NULL)
printf("First char without repetition: %c", head->c);
else
printf("No char matched");
return 0;
}
そしてそれは機能します（ただし、リンクされたリストのプログラムの最後でメモリを解放しませんでした）。基本的に、文字がまだ見つからない場合は 0、一度見つかった場合は 1 (そして末尾の位置でリンクされたリストに追加されます)、少なくとも 2 回出現する場合は 2 のハッシュテーブルを保持します。 (そして、リンクされたリストによって削除する必要があります)。
big-O 表記を使用したこのプログラムの計算の複雑さは?
このアルゴリズムは要素ごとに 1 回渡すだけなので、O(n) だと思いますが、リンクされたリスト内の値を削除するには (最悪の場合)、追加の O(k^2) が必要になります。ここで、k は要素の長さです。アルファベット使用。O(n+k^2) のようなものは私の選択です。文字列が非常に長く、アルファベットが制限されている場合、アルゴリズムは非常に効率的になります。