leetcode：389. 找不同

一、题目

函数原型：char findTheDifference(char * s, char * t)

二、思路

作者原先的思路是先将两个字符串从小到大排序，然后两个字符串依次比较。若出现字符串t中的元素和字符串s不相等，则说明该元素就是被添加的字母。

但是，该算法时间上仅仅击败13.33%的人，效率极低。

int cmp(const void *e1,const void *e2)
{return *(char*)e1 - *(char*)e2;
}char findTheDifference(char * s, char * t){int sz1=strlen(s);int sz2=strlen(t);qsort(s,sz1,1,cmp);qsort(t,sz2,1,cmp);int i=0;for(i=0;i<sz1;i++){if(s[i]!=t[i]&&s[i]==t[i+1]){return t[i];}}return t[i];
}

下面介绍几种时间效率比较高的算法：

思路1：

利用找单身狗的思想，详见：《leetcode：136. 只出现一次的数字（找单身狗）》

将两个字符串全部进行异或运算，最后得到的就是只出现一次的字母，即被添加的字母

char findTheDifference(char* s, char* t) {char result=0;int sz1=strlen(s);int sz2=strlen(t);for(int i=0;i<sz1;i++){result^=s[i];}for(int i=0;i<sz2;i++){result^=t[i];}return result;
}

思路2：

用字符串t的字母总和减去字符串s的字母总和，因为相同字母相减结果为0，所以剩下的就是被添加的字母

char findTheDifference(char* s, char* t) {char result=0;int sz1=strlen(s);int sz2=strlen(t);for(int i=0;i<sz2;i++){result+=t[i];}for(int i=0;i<sz1;i++){result-=s[i];}return result;
}

思路3：

设置一个大小为26的数组（初始值为0），字母 a-z 分别对应位置 0-25 ，通过各字母通过减去a可以转换为对应的数字。先遍历字符串s，当某个字母出现其对应的位置就+1；再遍历字符串t，当某个字母出现其对应位置就-1。最后若某个位置变为了-1，说明该字母在s中未出现，在t中出现了，该字母就是被添加的字母，返回该字母即可。

char findTheDifference(char* s, char* t) 
{int nums[26]={0};memset(nums,0,sizeof(nums));int sz1=strlen(s);int sz2=strlen(t);for(int i=0;i<sz1;i++){nums[s[i]-'a']++;}for(int i=0;i<sz2;i++){nums[t[i]-'a']--;if(nums[t[i]-'a']==-1)return t[i];}return ' ';
}