搜索第一个非重复字符

Question

程序在字符数组中找到第一个非重复字符，数组只包含小写字母。

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
char a2z[26]={0};//Hash

char input[100] = "abcbbbcdegh";//sample input, only small case english alphabets
int n = strlen(input);

for(int i=0; i<n; ++i)
{
    if( a2z[  input[i]-97 ]<0 )
    {
         //do nothing, this character has already repeated
    }
    else if( a2z[  input[i]-97 ]==0 )
    {
        a2z[ input[i]-97 ] = i+1; //character encoutered first time
    }
    else
    {
        a2z[ input[i]-97 ] = -(i+1); //repeating character
    }
}

int minAt=n+1;
for(int i=0; i<26; ++i) //finding first non-negative character in the Hash
{
    if( (a2z[i]>0) && (a2z[i]<minAt) )
    {
        minAt=a2z[i];
    }
}

if( minAt == n+1 )
    cout<<"\n\n no unique character";
else
    cout<<"\n\nFirst unique character is "<<input[minAt-1]<<" at position "<<minAt-1<<endl; 
}  

产出:：

First unique character is a at position 0

这里，我使用了一个字符数组(即a2z)，该数组由26个字符组成，用零初始化，并将其用作Hash。

如果a2z我为0表示(英文字母表的) ith字符，则a2z我的正值表示在a2z我-1位置只遇到过一次，负值表明它已经重复了。

请检查这段代码。

Answer 1

就这个计划而言，没有太多的非意见改进的可能。

然而，有几个正确性/(微观)优化点：

char a2z[26]

煤焦可能不够大。

a2z[ input[i]-97 ] = i+1;
a2z[ input[i]-97 ] = -(i+1);

i = 0 ... strlen(input)-1因此min(i) = 0和max(i) = strlen(input)。

签名字符c可以是：-128 <= c <= 127，因此，您的实现仅限于strlen(input) <= 127。

隐式双环

通常，strlen()的实现大致如下所示：

size_t strlen(const char* str)
{
    size_t len = 0;
    while (str[len] != 0) {
        ++len;
    }
    return len;
}

因此，您的程序在字符串上循环了两次。

您可以更改循环以将strlen嵌入到代码中：

for(int i=0, const char* c = input; c != 0; ++i, ++c) {

这可以写得更清晰一点，但希望它能让人明白这一点。

(这也可能不是一个非常有意义的优化。它可能具有相同的特性，或者取决于循环的具体方式，这可能会导致性能更差。如果你试图进行微观优化的话，就需要考虑一下。)

风格古怪(无根据的公然观点)

这几个项目在正确性方面完全是武断的(基本上都是个人喜好)：

• 它是有效的，但是为了明确起见，我更喜欢使用the长形式的main()，并且总是包括一个return。
• 我也更喜欢在if和else语句的表达式周围使用大括号。这完全是个人偏好，但我发现它会产生更清晰、更少错误的代码
• #include<iostream> --我不知道在包含和文件之间没有空格是否有效。不管怎么说，我很少看到它是这样写的，而且看起来有点奇怪。
• a2z[ input[i]-97 ]在我看来有点奇怪。
• char input[100] = "abcbbbcdegh";可能是const char input[] = "abcbbbcdegh";

Answer 2

这是个坏习惯别再做了。

using namespace std;

一旦您的程序超过10行，它就开始增加复杂性，包括整个命名空间。所以最好不要这么做。养成现在不使用的习惯，否则改掉习惯是很难的。

不要在代码中添加错误的注释(实际上，尽量不要添加注释)。评论应该解释你想要达到的目标(或者可能的原因)(而不是如何)。代码解释了如何避免在注释中复制代码。在代码中最糟糕的是与代码不匹配的注释。

char a2z[26]={0};//Hash

这不是哈希。散列有一个非常具体的含义，而这不是您正在做的事情。

在声明数组时更喜欢使用[]。这意味着编译器将尝试为您设置数组的长度。

char input[100] = "abcbbbcdegh";//sample input, only small case english alphabets

当我们在这里的时候。停止在C++中使用C元素。学习使用C++结构，不要混淆语言。另一个你应该陷入的坏习惯。

int n = strlen(input);

C++有自己的string类。

std::string  input("abcbbbddddd");
// size is input.size()

学习如何使用迭代器。

for(int i=0; i<n; ++i)

它将允许您更多地使用您的代码。可能允许您的代码处理多个容器类型(而不仅仅是字符串)。但更重要的是，这是使用标准算法的第一步。

您所做的假设是您的输入只包含小写字母。你应该始终防御性地编码。您必须验证您的输入。

Answer 3

相同的程序有几处变化。首先，尝试重构您的函数，以便它们是小的，其次，经常使用case语句比使用级联语句更清楚。第三，“使用命名空间std”是一个坏习惯。在这样的小程序中使用可能是可以的，但是避免在较大的项目中污染您的全局命名空间。在可能的时候避免神奇的数字

#include<iostream>

char a2z[26]={0};

int process(char* input, int len) {
  for (int i=0; i<len; i++) {
    int c = input[i] - 'a';
    switch(a2z[c]) {
      case -1:
        continue;
      case 0:
        a2z[c] = i+1;
        break;
      default:
        a2z[c] = -1;
    }
  }
}

int findfirst(int min) {
  for(int i=0; i< sizeof(a2z); ++i) {
    if( a2z[i]>0 && a2z[i]<min ) min = a2z[i];
  }
  return min;
}

int main() {
  char input[] = "aabbbcbbbcddegghh";
  int n = sizeof(input);
  process(input, n);
  int minAt = findfirst(n+1);

  if( minAt > n )
    std::cout<<"no unique character"<<std::endl;
  else
    std::cout<<"First unique character is "
      <<input[minAt-1]
      <<" at position "<<minAt-1<<std::endl; 
}