【字符串】查找一個字符串中第一個只出現兩次的字符。比如:“abcdefabcdefabc”中第一個只出現兩次為‘d’,要求時間復雜度為O(N),空間復雜度為O(1) -开发者知识库

【字符串】查找一個字符串中第一個只出現兩次的字符。比如:“abcdefabcdefabc”中第一個只出現兩次為‘d’,要求時間復雜度為O(N),空間復雜度為O(1) -开发者知识库,第1张

問題描述:

查找一個字符串中第一個只出現兩次的字符。比如:“abcdefabcdefabc”中第一個只出現兩次為‘d’,要求時間復雜度為O(N),空間復雜度為O(1)。

分析問題:

方法1、O(N^2)
看到這道題時,最直觀的想法是從頭開始掃描這個字符串中的每個字符。當訪問到某字符時拿這個字符和后面的每個字符相比較,如果后面出現兩次該字符,那么該字符為第一個只出現兩次的字符(注:內存循環需要全部遍歷完字符)。如果字符串有n個字符,每個字符可能與后面的O(n)個字符相比較,因此這種思路時間復雜度是O(N^2)。

看代碼:O(N^2)

char* FindFirstTwo(char *str)
{
int i = 0, j = 0;
int len = strlen(str);
int count = 0;//記錄出現幾次
for (; i < len; i)
{
char tmp = str[i];
count = 1;
for (j = i 1; j < len; j)
{
if (tmp == str[j])
count ;
}
if (count == 2)
return str i;
}
return NULL;
}
void TestFindFirstTwo()
{
char str[] = "abcdefabcdefabc";
char *res = FindFirstTwo(str);
if (res)
cout << *res << endl;
}

方法2、
可以考慮到用空間來換取時間,遍歷一遍字符串時,可以記錄下字符次數。第二次遍歷,比較哈希表里面的出現的次數

bool FindFirstTwo2(char *str)
{
int len = strlen(str);
int hashtables[256] = { 0 };

//第一次遍歷
for (int i = 0; i < len; i)
{
hashtables[str[i]] ;
}

//第二次遍歷
for (int i = 0; i < len; i)
{
if (hashtables[str[i]] == 2)
{
cout << str[i] << endl;
return true;
}
}
return false;
}
void TestFindFirstTwo2()
{
char str[] = "abcdefabcdefabc";
bool flag = FindFirstTwo2(str);
}

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复