0

我编写了以下程序来回答这个问题

编写一个高效的函数来查找字符串中第一个不重复的字符。例如，“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 （并且应该被链表删除）。

这个程序的大 O 表示法的计算复杂度是多少？

由于这个算法每个元素只通过一次，我认为它是 O(n)，尽管删除链表中的值（在最坏的情况下可能）需要额外的 O(k^2)，其中 k 是使用的字母表。像 O(n+k^2) 这样的东西是我的选择，如果字符串很长并且字母表受到限制，算法就会变得非常有效。

4

2 回答 2

1

嗯，是的，从表面上看，这看起来很O(N)复杂，但是您通过使用动态分配引入了不良的低效率。

但是，因为您调用deleteNode并且必须搜索列表，所以您不再具有O(N)复杂性。

想想如果你有字符串会发生什么：

abcdefghijklmnopqrstuvwxyzzyxwvutsrqponmlkjihgfedcb

这具有大致的复杂性，O(N*(N-1)/2)因为每个deleteNode调用都必须扫描到剩余列表的末尾。

您真正需要做的就是扫描字符串一次并存储每个字符的索引（如果尚未找到），然后扫描该数组以查找最低索引。如果你喜欢，你可以使用一个索引-1来表示一个字符还没有遇到过。那将是复杂的O(2N)

于 2013-02-11T23:34:12.263 回答
1

从算法描述中：“它必须至少是 O(n)，因为在你读完所有字符之前，你不知道一个字符是否会重复。”，另请参阅：Find the first unrepeated character in a字符串。

在您的算法中，我看不到从链表中删除元素的 O(k^2) 复杂度。从链表中删除一个元素是 O(n) + O(1) = O(n)，其中 O(n) 是搜索，O(1) 是找到节点后的擦除。

由于链表最多只能包含 k 个元素，因此删除需要 O(k)。因为这是在 for-loop => O(n*k) 内。

由于 k 是常数 => O(n) 复杂度——但是，它可以以更简单的方式实现。同样，请参阅https://stackoverflow.com/a/2285561/592636（使用两个数组）。

于 2013-02-11T23:46:06.710 回答