This is the 7th day of my participation in the August Text Challenge.More challenges in August

Topic describes

Given a string, find its first non-repeating character and return its index. If it does not exist, return -1. Example: s ="leetcode"return0

s = "loveleetcode"return2Tip: You can assume that the string contains only lowercase letters. Source: LeetCode//leetcode-cn.com/problems/first-unique-character-in-a-stringCopyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.Copy the code

Ideas & CODE

1. Cycle of violence

When one day the cycle of violence can not solve the problem, I would rather give up the learning algorithm – plum cake

Using a double for loop to solve this problem is very clear:

  1. Converts a string to an array of characters
  2. Iterate over a character array
  3. The second layer of traversal compares the values of the outer layer traversal with values different from their own
  4. If the values are the same, skip the outer loop
  5. If not, return the index of the outer loop
  6. Returns if all characters are more than one- 1
public static int firstUniqChar(String s) {
    int res = -1;
    char[] chars = s.toCharArray();
    outer: for (int i = 0; i < chars.length; i++) {
        for (int j = 0; j < chars.length; j++) {
            if(i ! = j && chars[i] == chars[j]) {continue outer;
            }
        }
        res = i;
        break;
    }
    return res;
}
Copy the code

Although the time complexity is O(n^2), it still exceeds 72% of Java

2. Hash stores indexes

After writing double for, I couldn’t come up with another idea, so I looked at the TAG in the question and found that I could write it with hash.

  • First, we convert the string to an array of characters, putting all the characters as keys and indexes as valuesHashMapIn the
  • Iterate over a character array
    • If the element in the map is not empty and the index is equal to the current iterated index, then there is only one character in the string, return the index at that position and end the loop. Why is that? If we have the same character, the following character will overwrite the previous character, because we used the character as the key, and the index of the same character must be different.
    • If the index retrieved from the map by character does not match the current index, the key-value is removed from the hash table
public static int firstUniqChar(String s) {
    Map<Character, Integer> map = new HashMap<>();
    char[] chars = s.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        map.put(chars[i], i);
    }
    int res = -1;
    for (int i = 0; i < chars.length; i++) {
        if(map.get(chars[i]) ! =null && map.get(chars[i]) == i) {
            res = i;
            break;
        } else{ map.remove(chars[i]); }}return res;
}
Copy the code

The time is O(n), but it takes longer than the above algorithm