389. 找不同

四种解法

求和

reduce是在numeric头文件下的对容器进行累计操作的方法，默认是求和

1
return  (char)reduce(t.begin(), t.end()) - reduce(t.begin(),t.end());

时间复杂度On，空间复杂度O1

排序

1
2
3
4
5
6
7
8
9
10
11
12
13
ranges::sort(s);
	ranges::sort(t);
 
	int n = s.length();
	for (int i = 0; i < n; i++)
	{
		if (s[i] != t[i])
		{
			return s[i];
		}
	}
 
	return t.back();

时间复杂度OnlogN，空间复杂度O1

计数

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> cnt(26, 0);
        for (char ch: s) {
            cnt[ch - 'a']++;
        }
        for (char ch: t) {
            cnt[ch - 'a']--;
            if (cnt[ch - 'a'] < 0) {
                return ch;
            }
        }
        return ' ';


时间复杂度On，空间复杂度Oe，e = 26

位运算

1
2
3
4
5
6
7
8
9
int ret = 0;
      for (char ch: s) {
          ret ^= ch;
      }
      for (char ch: t) {
          ret ^= ch;
      }
      return ret;

时间复杂度On，空间复杂度O1