在字符串中找出第一个只出现一次的字符。经典C语言例题

原题要求:

在字符串中找出第一个只出现一次的字符。

如输入“abaccdeff”,则输出’b’。

 

思考过程:字符串中字符有很多,只出现一次的也有很多,最直接简单的方法就是记录下每个字符出现的个数,然后从第一个字符开始看,找出第一个只出现一次的字符。

程序实现:

方法一:当字符数组比较小时,便利每个元素:

 

/*  题目:在字符串中找出第一个只出现一次的字符。
   *   如输入“abaccdeff”,则输出'b'。
  */
#include<stdio.h>
#include<stdlib.h>
int find_f(char arr[],const int len)  //寻找函数
{
    int i, j, k;
    int arr1[20] = { 0 };     //定义一个储存每个字符出现次数的数组,
    for (i = 0; i < len; i++)   //对字符数组元素进行遍历,并记录该字符出现次数
    {
        k = 0;
        for (j = 0; j < len; j++)
        {
            if (arr[i] == arr[j])
                k++;
            arr1[i] = k;
        }
    }
    for (i = 0; i < len; i++)  //从第一个开始访问,找出第一个只出现一次的字符,返回该字符在原数组的下标
    {
        if (arr1[i] == 1)
        {
            return i;
        }
    }
    return len + 1;  //如果没有单独出现的字符,返回一个不是下标的数
}

int main()
{
    char arr[] = "abaccdeff";
    int len = sizeof(arr) / sizeof(arr[0]), c;
    c = find_f(arr, len);
    if (c > len)
        printf("这个字符串组数中没有只出现一次的字符\n");
    else
        printf("输入字符串中第一次出现的字符是:%c\n", arr[c]);
    system("pause");
    return 0;
}

 

 

方法二:当字符数组比较大时,记录每个字符出现的个数(用哈希表,具体方法:我们第一遍扫描这个数组时,每碰到一个字符,在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时,就能直接从哈希表中得到每个字符出现的次数了。)

代码:

 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define tableSize 256      //创建一个哈希表,因为ASCII码表中只有0~255共256个字符。

char First_Char(char* pString)
{
     if (!pString)    //输入不合法
        return 0;
    int hashTable[tableSize];
    for (int i = 0; i < tableSize; i++)
         hashTable[i] = 0;
    //确定字符串中每个字符出现的次数
    char* pHashKey = pString;
    while (*(pHashKey) != '\0')
        hashTable[*(pHashKey++)]++;
    //找到字符串中只出现一次的那个字符
    pHashKey = pString;
    while (*pHashKey != '\0')
    {
        if (hashTable[*pHashKey] == 1)
            return*pHashKey;
         pHashKey++;
    }
     //如果这个字符串为空,或者字符串中的每个字符都至少出现两次
     return 0;
    }

int main(void)
{
    char str[1000];  //这个函数是在字符串特别大时建议使用,故定义一个大小为1000的数组
    printf("请输入字符串:");
    gets(str);
    if (First_Char(str) == 0)
        printf("输入字符串中没有找到第一个只出现一次的字符!\n");
    else
        printf("输入字符串中第一个只出现一次的字符为:%c\n", First_Char(str));
    system("pause");
    return 0;
}

 

 

原题要求: 在字符串中找出第一个只出现一次的字符。
如输入abaccdeff,则输出…

 

 

题目:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。

题目:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。

 

 

看到这道题时,最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较,如果在后面没有发现重复的字符,则该字符就是只出现一次的字符。如果字符串有n个字符,每个字符可能与后面的O(n)个字符相比较,因此这种思路时间复杂度是O(n2)。我们试着去找一个更快的方法。

           我的思路是:

 

           如果要知道一个字符是否只出现过一次,必须遍历一次字符串知道所有字符出现过的情况,从前从后都可以。但在遍历中要用数组统计每个字符的出现次数,到最后将,再遍历一遍数组,得到出现次数为1的第一个字符,取出。

由于题目与字符出现的次数相关,我们是不是可以统计每个字符在该字符串中出现的次数?要达到这个目的,我们需要一个数据容器来存放每个字符的出现次数。在这
个数据容器中可以根据字符来查找它出现的次数,也就是说这个容器的作用是把一个字符映射成一个数字。在常用的数据容器中,哈希表正是这个用途。

          空间复杂度:O(1)        

为了解决这个问题,我们可以定义哈希表的键值(key)是字符,而值(value)是该字符出现的次数。同时我们还需要从头开始扫描字符串两次。第一次扫描字符串时,每扫描到一个字符就在哈希表的对应项中把次数加1
。接下来第二次扫描时,每扫描到一个字符就能从哈希表中得到该字符出现的次数。这样第一个只出现一次的字符就是符合要求的输出。

          时间复杂度:O(n)

 

 

哈希表是一种比较复杂的数据结构。由于比较复杂,STL中没有实现哈希表,因此需要我们自己实现一个。但由于本题的特殊性,我们只需要一个非常简单的哈希表就能满足要求。由于字符(**char)是一个长度为8的数据类型,因此总共有可能256种可能**。于是我们创建一个长度为256的数组,每个字母根据其ASCII码值作为数组的下标对应数组的对应项,而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256,以字符ASCII码为键值的哈希表。

这是别人通过HashTable来完成的,殊途同归!

 

           REF:

我们第一遍扫描这个数组时,每碰到一个字符,在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时,就能直接从哈希表中得到每个字符出现的次数了。

        看到这道题时,最直观的想法是从头开始扫描这个字符串中的每个字符。当访问到某字符时拿这个字符和后面的每个字符相比较,如果在后面没有发现重复的字符,则该字符就是只出现一次的字符。如果字符串有n个字符,每个字符可能与后面的O(n)个字符相比较,因此这种思路时间复杂度是O(n2)。我们试着去找一个更快的方法。

 

       
由于题目与字符出现的次数相关,我们是不是可以统计每个字符在该字符串中出现的次数?要达到这个目的,我们需要
一个数据容器来存放每个字符的出现次数。在这个数据容器中可以根据字符来查找它出现的次数,也就是说这个容器的作用是把一个字符映射成一个数字。在常用的
数据容器中,哈希表正是这个用途。
      

参考代码如下:

       
哈希表是一种比较复杂的数据结构。由于比较复杂,STL中没有实现哈希表,因此需要我们自己实现一个。但由于本题的特殊性,我们只需要一个非常简单的哈希表就能满足要求。由于字符(char)是一个长度为8的数据类型,因此总共有可能256
种可能。于是我们创建一个长度为256的数组,每个字母根据其ASCII码值作为数组的下标对应数组的对应项,而数组中存储的是每个字符对应的次数。这样我们就创建了一个大小为256,以字符ASCII码为键值的哈希表。(并不仅限于英文字符,所以这里要考虑256种可能)。
我们第一遍扫描这个数组时,每碰到一个字符,在哈希表中找到对应的项并把出现的次数增加一次。这样在进行第二次扫描时,就能直接从哈希表中得到每个字符出现的次数了。
   

///////////////////////////////////////////////////////////////////////
// Find the first char which appears only once in a string
// Input: pString - the string
// Output: the first not repeating char if the string has, otherwise 0
///////////////////////////////////////////////////////////////////////
char FirstNotRepeatingChar(char* pString)
{
      // invalid input
      if(pString == NULL)
            return '\0';

      // get a hash table, and initialize it 
      const int tableSize = 256;
      unsigned int hashTable[tableSize];
      for(unsigned int i = 0; i < tableSize; ++ i)
            hashTable[i] = 0;

      // get the how many times each char appears in the string
      char* pHashKey = pString;
      while(*(pHashKey) != '\0')
            hashTable[*(pHashKey++)] ++;

      // find the first char which appears only once in a string
      pHashKey = pString;
      while(*pHashKey != '\0')
      {
            if(hashTable[*pHashKey] == 1)
                  return *pHashKey;

            pHashKey++;
      }

      // if the string is empty 
      // or every char in the string appears at least twice
      return '\0';
} 

        参考代码如下:

 

#include "stdio.h" 
#include "string.h" 
#include "stdlib.h"
char FirstNotRepeatingChar(char* pString) 
{ 
    //输入不合法
    if(!pString)
        return 0;

    //创建一个哈希表,并初始化
    const int tableSize = 256;     
    int hashTable[tableSize];     
    for(int i = 0; i < tableSize; i++)    
        hashTable[i] = 0;

    //确定字符串中每个字符出现的次数    
    char* pHashKey = pString;     
    while(*(pHashKey) != '\0')         
        hashTable[*(pHashKey++)]++; 

    //找到字符串中只出现一次的那个字符    
    pHashKey = pString;   
    while(*pHashKey != '\0')    
    {
        if(hashTable[*pHashKey] == 1)
            return *pHashKey;
        pHashKey++;
    }

    //如果这个字符串为空,或者字符串中的每个字符都至少出现两次
    return 0;
}

int main(void)
{
    char str[1000];   
    printf("请输入字符串:");
    gets(str);
    if(FirstNotRepeatingChar(str)==0)
        printf("输入字符串中没有找到第一个只出现一次的字符!\n");
    else
        printf("输入字符串中第一个只出现一次的字符为:%c\n",FirstNotRepeatingChar(str));
    system("pause");
    return 0;
}

如在一个数组中,寻找唯一的一个只出现一次的数。

 

#include<iostream>
using namespace std;

int SingleNumber(int arr[] , int length)
{
    int i , xor;
    for(xor = 0 , i = 0 ; i < length ; ++i)
        xor = xor ^ arr[i];

    return xor;
}

int main()
{
    int arr[] = {2 , 1 , 2 , 1 , 3 , 4 , 3};
    int length = sizeof(arr)/ sizeof(int);

    cout<<SingleNumber(arr , length)<<endl;

    return 0;
}

 

 

           也可以通过原理相同的位图的形式来完成,很巧妙!

 

int main()   
{   
    char c[]="abaccdeff";  
    int bit_map[256]={0};  
    int i=0;  
    int j=0;  
    for(;i<strlen(c);++i)  
        bit_map[c[i]-' ']++;  
    j=strelen(c);  
    for(i=0;i<j;++i)  
    {  
        if(bit_map[c[i]-' ']==1)  
        {  
            printf(" %c ",c[i]);  
            break;  
        }  
    }  
    if(i>=j)  
        printf("No ele to the rule\n");   
    return 0;  
}   

不管是通过哈希表还是位图实现,都是O(n)的时间复杂度跟O(1)的空间复杂度。
 

Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注