迹忆客 专注技术分享

在本文中，您将学习如何在 C++ 中查找字符串中的第一个重复字符。 您将学习实现此目的的三种方法：散列技术、暴力方法和算法的编写。

在 C++ 中查找字符串中的第一个重复字符

有两种方法可以尝试编写算法； 第一种方法是从左到右遍历字符串，第二种方法是从右到左遍历字符串并跟踪访问的字符。 第二种方法在性能上优于任何其他方法，因为它通过进行更少的比较来提高效率。

排序算法可以帮助您在 O(n Log n) 时间内找到字符串中的第一个重复字符。 但是，您可以循环遍历字符串并使用 ASCII 代码对字符进行哈希处理，在哈希数组上运行循环，并找到任何重复字符的最小位置。

代码示例：

#include <iostream>

using namespace std;

#define numberChar 256

// left most string
int farLeftStr(string& primeStr)
{
    // represents the first index
    int IndexNum[numberChar];

    for (int i = 0; i < numberChar; i++)
        IndexNum[i] = -1;

    // represents the resultIndexNum
    int resultStr = INT_MAX;

    for (int i = 0; i < primeStr.length(); i++) {
        if (IndexNum[primeStr[i]] == -1)
            IndexNum[primeStr[i]] = i;
        else
            resultStr = min(resultStr, IndexNum[primeStr[i]]);
    }
    return (resultStr == INT_MAX) ? -1 : resultStr;
}

int main()
{
    string primeStr = "HouseOfTheDragons";
    int left = farLeftStr(primeStr);

    if (left == -1)
        cout << "All characters are distinct or string is empty ";
    else
        cout<< "The first repeating character is: " << primeStr[left];
    return 0;
}

输出:

The first repeating character is: o

将每个字符的第一个索引初始化为 -1 时，从左到右遍历字符串是可行的。 您可以将重复字符的第一个或最左边的索引（如果遇到它）与当前结果进行比较。

此外，您可以通过研究每个字符并在字符串的其余部分中搜索相同的字符，使用 O(N²) 复杂度来解决此问题。

使用哈希技术在 C++ 中查找字符串中的第一个重复字符

Count 数组可以找到第一个重复字符并保存字符串中重复字符的计数。

散列技术由四个主要步骤组成。

1. 创建一个哈希表。
2. 扫描字符。
3. 如果哈希表中不存在字符，则将其插入该哈希表中。
4. 否则，返回该字符作为重复项。

代码示例：

#include<iostream>

// hashing function object type
#include<unordered_set>

using namespace std;

char getRepeatingChar(string &str)
{
   unordered_set<char> hashObj;

   for (int i=0; i<str.length(); i++)
   {
      char repChar = str[i];
      if (hashObj.find(repChar) != hashObj.end())
         return repChar;
      else
          hashObj.insert(repChar);
   }
   return '\0';
}

int main () {
   string expStr = "GameOfThrones";
   cout << "The first repeating character is: " << getRepeatingChar(expStr);
}

输出:

The first repeating character is: e

此问题的另一个著名变体是，如果计数等于 1，则通过打印结果来打印字符串中的第一个唯一或不重复的字符。 作为原始技术的扩展变体，可以打印字符串中的所有重复字符，但它不像基本哈希方法那么简单。

由于需要用户创建Count数组，因此该方法的时间复杂度为O(n)。 在最坏的情况下，没有重复和额外的空间，其时间复杂度将为O(1)。

在 C++ 中使用暴力法查找字符串中的第一个重复字符

这是一种简单的方法，使程序员能够检查字符串中的每个字符以查找重复字符并输出相应的结果。 如果到达结束字符串或者扫描到最后一个字符，则没有找到重复字符，默认没有重复字符。

在最坏的情况下，在没有重复的情况下，其时间复杂度为O(n2)，在最好的情况下，时间复杂度为O(1)，这表示第二个位置存在重复字符。 由于您需要一个占用恒定内存量的计数数组，因此它比暴力方法要多，并且它占用的总额外空间是 O(1)，即恒定的。

代码示例：

#include<iostream>

using namespace std;

int main () {
   string expStr = "Hello World!";
   string primeExp = "";

   // check the boundary of the `expStr` string
   if(expStr == primeExp)
   {
       cout << "The string is empty!";
   }

   for(int a = 0; expStr[a] != '\0';  a++)
   {
       for(int b=a+1; expStr[b] != '\0'; b++)
       {
           if(expStr[a] == expStr[b])
           {
               cout << "The first repeating character is: " << expStr[a];
           }
           break;
       }
   }
}

输出:

The first repeating character is: l