Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
670 views
in Technique[技术] by (71.8m points)

java - First unique character in a string using LinkedHashMap

Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode"
return 2.

In my solution I can find the character itself but I am looking to get the index of the character! How would I change my code to get the index using LinkedHashMap? And thank you in advance.

public static void firstNonRepeatingString(String str) {
    LinkedHashMap<Character, Integer> lhm = new LinkedHashMap<>();
    char[] charArray = str.toCharArray();
    for (char character : charArray) {
        if (lhm.get(character) == null) {
            lhm.put(character, 1);
        } else {
            lhm.put(character, lhm.get(character) + 1);
        }
    }

    for (Map.Entry<Character, Integer> entry : lhm.entrySet())
        if (entry.getValue() == 1) {
            System.out.print(entry.getKey());
            break;
        }
}
firstNonRepeatingString("aaabcccddeggf"); 

This will print b, but I want to print 3.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

My solution using a map of records.... Requires Java 14 or greater and enabling preview features. Seems a little verbose, but basically what the code below does is walk through the array of characters in the inputted String and create a record {character, index, count}. Then, it puts the created record on the map. Since put returns the previous value of that key, the code then "merges" the two records and replaces the entry with a new record that keeps the character and lower index and increments the higher count by one.

Lastly, it uses a stream to filter all entries in the map to only those that have a count of 1 and then returns the entry with the lowest index.

When inputting "loveleetcode" the code prints out the entry with the lowest index that has a count of 1:

v=CharacterCount[character=v, index=2, count=1]

Keep in mind that the record doesn't really need the character (since the key is the character). All you need in the record is the lowest index for that character and the count.


import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;

public class FirstUniqueCharacterDemo {
    
    public static void main (String[] args) {
//      String input1 = "leetcode"; // return 0
        String input1 = "loveleetcode"; // return 2

        Map<Character, CharacterCount> charMap = new LinkedHashMap<>();
        
        for (int i = 0; i < input1.length(); i++) {
            
            char c = input1.charAt(i);

            CharacterCount current = new CharacterCount(c, i, 1); // records are immutable
            CharacterCount previous = charMap.put(c, current);
            if(previous != null) {
                current = current.merge(previous); // combine records (add 1 to count and keep lower index)
                charMap.replace(c, current);
            }
        }

        Entry<Character, CharacterCount> lowestIndex = charMap.entrySet().stream()
            .filter(recordsWithOneEntry -> recordsWithOneEntry.getValue().count() == 1)
            .min(Map.Entry.comparingByValue(Comparator.comparingInt(CharacterCount::index))).orElse(null); // This will return either the CharacterCount record or null if none are found with a count of 1.
        
        System.out.println(lowestIndex);
        
    }

    public static record CharacterCount(char character, int index, int count) {
        public boolean isIndexGreater(int index) {
            return this.index > index;
        }
        
        public CharacterCount merge(CharacterCount cc) {
            int index = (isIndexGreater(cc.index()) ? cc.index : this.index);
            int count = this.count() > cc.count ? this.count() + 1 : cc.count() + 1;
            char c = this.character();
            return new CharacterCount(c, index, count);
        }
    }
}

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...