“This is the 10th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

πŸ“’ preface

πŸš€ Algorithm πŸš€
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 70th day of continuous clocking of force button algorithm 🎈!
πŸš€ Algorithm πŸš€

🌲 The first unique character in a string

Given a string, find its first non-repeating character and return its index. If none exists, -1 is returned.

Example 1:

s = "leetcode"return0

s = "loveleetcode"return2
Copy the code

Tip:

  • You can assume that the string contains only lowercase letters.

🌻 c # method

An array holds the number of characters in the current string

Code:

public class Solution {
public int FirstUniqChar(string s) {

    int[] arr=new int[26];  // An array of 26 letters
    for(int i=0; i<s.Length; i++) { arr[s[i]-'a'] + =1;  / / a - 0 b - 1..................... The corresponding digit is +1
    }
    for(int i=0; i<s.Length; i++) {if(arr[s[i]-'a'] = =1)  // When the position is 1
        {
            returni; }}return - 1; }}Copy the code

The execution result

By execution time:64Ms, beat out all Java commits99.50% user memory consumption:43.4MB, beat out all Java commits16.50% of the userCopy the code

🌻Java method: Use hash table to store frequency

A string can be traversed twice by train of thought parsing.

In the first run, we use a hash map to count the number of occurrences of each character in the string.

On the second traverse, we return the index of a character that occurs only once as long as it is traversed, or βˆ’1 at the end of the traverse.

Code:

class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> frequency = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            if (frequency.get(s.charAt(i)) == 1) {
                returni; }}return -1; }}Copy the code

The execution result

By execution time:26Ms, beat out all Java commits39.26% user memory consumption:38.2MB, beat out all Java commits88.05% of the userCopy the code

Complexity analysis

: time complexity O (n) space complexity: O (| Ξ£ |)Copy the code

πŸ’¬ summary

  • Today is the seventy day of the buckle algorithm clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!