题意

给n个字符，求其中首个只出现一次的字符是什么

限制，n不大于1000

方法

朴素实现

注意到n很小，我们遍历字符串，对于每一个位置再次遍历字符串，检查是否出现过，注意双重for循环时坐标相等需要跳过

以样例字符串 asdfasdfo 为例

找到字符o

代码

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i = (a);i<(b);i++)
using namespace std;
int main(){
    char s[1010];
    while(~scanf("%s",s)){
        int n = strlen(s);
        int idx = -1;
        rep(i,0,n){ // 遍历字符串
            bool exist = false;
            rep(j,0,n){ // 找是否出现过
                if(i == j)continue; 
                if(s[i] == s[j]){ // 出现过
                    exist = true;
                }
            }
            if(!exist){ // 未出现过
                idx = i; // 记录坐标
                break;
            }
        }
        if(idx == -1){
            printf("-1\n");
            continue;
        }
        printf("%c\n",s[idx]); // 输出字符
    }
    
    return 0;
}

复杂度分析

时间复杂度: 最坏情况，两层for都是字符串长度，所以时间复杂度为$O(n^2)O(n^2)$

空间复杂度: 主要是字符串本身储存，为$O(n)O(n)$

扫两遍

代码

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i = (a);i<(b);i++)
using namespace std;
int main(){
    char s[1010];
    while(~scanf("%s",s)){
        map<char,int> cnt; // 字符出现计数
        int n = strlen(s);
        rep(i,0,n){
            cnt[s[i]]++; // 计数+1
        }
        int idx = -1;
        rep(i,0,n){
            if(cnt[s[i]] == 1){ // 只出现一次
                idx = i;
                break;
            }
        }
        if(idx == -1){
            printf("-1\n");
            continue;
        }
        printf("%c\n",s[idx]); // 输出字符
    }
    
    return 0;
}

复杂度分析

时间复杂度: 对字符串扫了两遍，每次查询最差$log(n)log(n)$, 所以时间复杂度为$O(n\cdot log(n))O(n\; \backslash cdot\; log(n))$

空间复杂度: 主要是字符串储存和统计储存，所以空间复杂度为$O(n)O(n)$