题解 | #第一个只出现一次的字符#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param str string字符串
 * @return int整型
 */
int FirstNotRepeatingChar(char* str) {
    // write code here
    struct node {
        int time;
        int location;
    };
    int len = strlen(str);
    struct node* arr = (struct node*)calloc(60, sizeof(struct node));
    //arr[]数组用于存放字母出现的次数和出现的首位置，所以大小选>=57（查ASCII表可知）均可；

    for (int i = 0; i < len; i++) {
        if (arr[str[i] - 'A'].time == 0) {
            arr[str[i] - 'A'].time++;
            arr[str[i] - 'A'].location = i;
        } else {
            arr[str[i] - 'A'].time++;
            //arr[str[i] - 'A'].location = -1;
        }//仅保留首次出现的下标
    }
    int* temp = (int*)calloc(len, sizeof(int));
    //temp[]数组用于存放字符串中出现仅一次的字母的下标，所以大小<=len
    int size = 0;//temp的实际有效的大小。即字符串中出现仅一次的字母的个数

    for (size_t i = 0; i < 60; i++) {
        if (arr[i].time == 1) {
            temp[size++] = arr[i].location;
        }
    }
    if (size == 0) {
        return  -1;
    }

    int min = 10000;
    for (size_t i = 0; i < size; i++) {
        if (temp[i] < min) {
            min = temp[i];
        }
    }
    //找出下标最小值并返回

  return min;
}

采用计数排序，空间复杂度O(n)，时间复杂度也是O(n)。

同时，也可不用temp数组记录下标，参照官方做法再次遍历字符串即可

• step 1：遍历一次字符串，对于每个字符，放入哈希表中统计出现次数。
• step 2：再次遍历字符串，对于每个字符，检查哈希表中出现次数是否为1，找到第一个即可。
• step 3：遍历结束都没找到，那就是没有，返回-1.