Leetcode daily question: the first unique character in the string

link ： The first unique character in the string

（ notes ： The prompt string of this question only contains lowercase letters )

Conventional thinking ： Each character is traversed once , Find out whether there are the same letters in the string .( But in the worst case, the time complexity is O(n^2), So... Is not recommended here ）

Code ：

class Solution {
    
public:
    int firstUniqChar(string s) {
    
        // Conventional thinking ： Each time, we iterate to find whether there are equal , Time complexity O(n^2), Not recommended 
        for(size_t i = 0; i < s.size(); i++)
        {
    
        	// use flag Mark with , If it becomes 0 The description has the same 
            int flag = 1;
            for(size_t j = 0; j < s.size(); j++)
            {
    
            	// If the subscripts are the same, no comparison is required 
                if(j == i)
                    continue;
                if(s[j] != s[i])
                    continue;
                else
                {
    
                    flag = 0;
                    break;
                }
            }
            if(flag == 1)
                return i;
        }
        return -1;
    }
};

---

Another way to think about it ： Using the idea of counting and sorting , Count the number of occurrences of each letter in the string , Then add the first count array as 1 Letter return of .

notes ： The time complexity of this idea is O(N).

Code ：

class Solution {
    
public:
    int firstUniqChar(string s) {
    
        //  The time complexity is O(n)
        //  Using the idea of counting and sorting , First count the number of times each letter appears 
        int arr[26] = {
    0};
        for(size_t i = 0; i < s.size(); i++)
        {
    
            arr[s[i] - 'a']++;
        }

        // lookup s In the corresponding arr Whether the number of occurrences is once 
        for(size_t i = 0; i < s.size(); i++)
        {
    
            if(arr[s[i] - 'a'] == 1)
                return i;
        }

        return -1;
    }
};