Java 查找字符串中的第一个非重复字符

Find the first non repeating character in a string

提问by Jonathan Bishop

I m writing a method to find the first non repeating character in a string. I saw this method in a previous stackoverflow question

我正在编写一种方法来查找字符串中的第一个非重复字符。我在之前的 stackoverflow 问题中看到了这个方法

public static char findFirstNonRepChar(String input){
 char currentChar = '
public static Character getFirstNotRepeatedChar(String input) {

    byte[] flags = new byte[256]; //all is initialized by 0 

    for (int i = 0; i < input.length(); i++) { // O(n)
        flags[(int)input.charAt(i)]++ ;
    }

    for (int i = 0; i < input.length(); i++) { // O(n)
        if(flags[(int)input.charAt(i)] > 0)
            return input.charAt(i);
    }

    return null;
}
';
 int len = input.length();
 for(int i=0;i<len;i++){
    currentChar = input.charAt(i);
    if((i!=0) && (currentChar!=input.charAt(i-1)) && (i==input.lastIndexOf(currentChar))){
        return currentChar;
    }
 }
 return currentChar;
}

I came up with a solution using a hashtable where I have two for loops (not nested) where I interate through the string in one loop writing down each occurance of a letter (for example in apple, a would have 1, p would have 2, etc.) then in the second loop I interate through the hashtable to see which one has a count of 1 first. What is the benefit to the above method over what I came up with? I am new to Java does having two loops (not nested) hinder time complexity. Both these algorithms should have O(n) right? Is there another faster, less space complexity algorithm for this question than these two solutions?

我想出了一个使用哈希表的解决方案，其中我有两个 for 循环（非嵌套），我在一个循环中通过字符串进行交互，写下每个字母的出现（例如在苹果中，a 将有 1，p 将有 2等）然后在第二个循环中，我通过哈希表进行交互以查看哪个先计数为 1。与我提出的方法相比，上述方法有什么好处？我是 Java 新手，确实有两个循环（非嵌套）阻碍了时间复杂度。这两种算法都应该有 O(n) 对吗？对于这个问题，还有比这两个解决方案更快、空间复杂度更低的算法吗？

采纳答案by STaefi

As you asked if your code is from O(n)or not, I think it's not, because in the for loop, you are calling lastIndexOfand it's worst case is O(n). So it is from O(n^2).

当你问你的代码是否来自O(n)或不是时，我认为它不是，因为在 for 循环中，你正在调用lastIndexOf并且最坏的情况是O(n). 所以它来自O(n^2).

About your second question: having two loops which are not nested, also makes it from O(n).

关于你的第二个问题：有两个不嵌套的循环，也使它从O(n).

If assuming non unicode characters in your input String, and Uppercase or Lowercase characters are assumed to be different, the following would do it with o(n) and supports all ASCII codes from 0to 255:

如果假设输入字符串中的非 unicode 字符，并且假设大写或小写字符不同，则以下将使用 o(n) 执行此操作并支持从0to 的所有 ASCII 代码255：

public static Character findNonRepeatingChar(String x)
{
    HashSet<Character> validChars = new HashSet<>();
    HashSet<Character> invalidChars = new HashSet<>(); 

    char[] array = x.toCharArray();
    for (char c : array)
    {
        if (validChars.contains(c))
        {
            validChars.remove(c);
            invalidChars.add(c);
        }
        else if (!validChars.contains(c) && !invalidChars.contains(c))
        {
            validChars.add(c);
        }
    }

    return (!validChars.isEmpty() ? validChars.iterator().next() : null);
}

Thanks to Konstantinos Chalkiashint about the overflow, if your input string has more than 127 occurrence of a certain character, you can change the type of flagsarray from byte[]to int[]or long[]to prevent the overflow of bytetype.

感谢Konstantinos Chalkias关于溢出的提示，如果您的输入字符串出现超过 127 次某个字符，您可以将flags数组的类型从更改byte[]为int[]或long[]以防止byte类型溢出。

Hope it would be helpful.

希望它会有所帮助。

回答by Hatefiend

Okay I misread the question initially so here's a new solution. I believe is this O(n). The contains(Object)of HashSetis O(1), so we can take advantage of that and avoid a second loop. Essentially if we've never seen a specific charbefore, we add it to the validCharsas a potential candidate to be returned. The second we see it again however, we add it to the trash can of invalidChars. This prevents that char from being added again. At the end of the loop (you haveto loop at least once no matter what you do), you'll have a validCharshashset with namount of elements. If none are there, then it will return nullfrom the Character class. This has a distinct advantage as the charclass has no good way to return a 'bad' result so to speak.

好的，我最初误读了这个问题，所以这是一个新的解决方案。我相信这是 O(n)。所述contains(Object)的HashSet是O（1），所以我们可以利用这一点，并避免第二环路。基本上，如果我们以前从未见过特定的char，我们会将其添加到 中validChars作为要返回的潜在候选者。然而，当我们再次看到它时，我们将它添加到invalidChars. 这可以防止再次添加该字符。在循环结束时（你有循环至少一次，不管你做什么），你就会有一个validChars用一个HashSetn元素的量。如果没有，那么它将null从 Character 类返回。这具有明显的优势，因为char该类没有好的方法可以返回“坏”结果。

public static char findFirstNonRepChar(String string) {
    Map<Integer,Long> characters = string.chars().boxed()
            .collect(Collectors.groupingBy(Function.identity(), LinkedHashMap::new, Collectors.counting()));
    return (char)(int)characters.entrySet().stream()
            .filter(e -> e.getValue() == 1L)
            .findFirst()
            .map(Map.Entry::getKey)
            .orElseThrow(() -> new RuntimeException("No unrepeated character"));
}

回答by Olivier Grégtheitroade

The algorithm you showed is slow: it looks for each character in the string, it basically means that for each character you spend your time checking the string twice!! Huge time loss.

您展示的算法很慢：它查找字符串中的每个字符，这基本上意味着对于每个字符，您都花时间检查字符串两次！！巨大的时间损失。

The best naive O(n) solution basically holds all the characters in order of insertion (so the firstcan be found) and maps a mutable integer to them. When we're done, analyzing, we go through all the entries and return the first character that was registered and has a count of 1.

最好的原始 O(n) 解决方案基本上按插入顺序保存所有字符（因此可以找到第一个）并将可变整数映射到它们。完成分析后，我们遍历所有条目并返回已注册且计数为 1 的第一个字符。

There are no restrictions on the characters you can use. And AtomicIntegeris available with import java.util.concurrent.atomic.AtomicInteger.

您可以使用的字符没有限制。并且AtomicInteger可与import java.util.concurrent.atomic.AtomicInteger.

Using Java 8:

使用 Java 8：

public static char findFirstNonRepChar(String string) {
  Map<Character, AtomicInteger> characters = new LinkedHashMap<>(); // preserves order of insertion.
  for (int i = 0; i < string.length(); i++) {
    char c = string.charAt(i);
    AtomicInteger n = characters.get(c);
    if (n == null) {
      n = new AtomicInteger(0);
      characters.put(c, n);
    }
    n.incrementAndGet();
  }
  for (Map.Entry<Character, AtomicInteger> entry: characters.entries()) {
    if (entry.getValue().get() == 1) {
      return entry.getKey();
    }
  }
  throw new RuntimeException("No unrepeated character");
}

Non Java 8 equivalent:

非 Java 8 等效项：

package com.java.teasers.samples;  
import java.util.Map;  
import java.util.HashMap;  
public class NonRepeatCharacter {  
    public static void main(String[] args) {  
        String yourString = "Hi this is javateasers";//change it with your string  
        Map<Character, Integer> characterMap = new HashMap<Character, Integer>();  
        //Step 1 of the Algorithm  
        for (int i = 0; i < yourString.length(); i++) {  
            Character character = yourString.charAt(i);  
            //check if character is already present  
            if(null != characterMap.get(character)){  
                //in case it is already there increment the count by 1.  
                characterMap.put(character, characterMap.get(character) + 1);  
            }  
            //in case it is for the first time. Put 1 to the count  
            else  
                characterMap.put(character, 1);  
        }  
        //Step 2 of the Algorithm  
        for (int i = 0; i < yourString.length(); i++) {  
            Character character = yourString.charAt(i);  
            int count = characterMap.get(character);  
            if(count == 1){  
                System.out.println("character is:" + character);  
                break;  
            }  
        }  
    }  
}  

回答by Karan Khanna

In case of two loops (not nested) the time complexity would be O(n).

在两个循环（非嵌套）的情况下，时间复杂度为 O(n)。

The second solution mentioned in the question can be implemented as:

问题中提到的第二种解决方案可以实现为：

We can use string characters as keys to a map and maintain their count. Following is the algorithm.

我们可以使用字符串字符作为映射的键并保持它们的计数。下面是算法。

1.Scan the string from left to right and construct the count map.

1.从左到右扫描字符串并构建计数图。

2.Again, scan the string from left to right and check for count of each character from the map, if you find an element who's count is 1, return it.

2.再次从左到右扫描字符串并检查映射中每个字符的计数，如果找到计数为1的元素，则返回它。

/*
 * It works for lowercase a-z
 * you can scale it to add more characters
 * eg use 128 Vs 26 for ASCII or 256 for extended ASCII 
 */
public static char getFirstNotRepeatedChar(String input) {

    boolean[] charsExist = new boolean[26];
    boolean[] charsNonUnique = new boolean[26];

    for (int i = 0; i < input.length(); i++) {
        int index = 'z' - input.charAt(i);
        if (!charsExist[index]) {
            charsExist[index] = true;
        } else {
            charsNonUnique[index] = true;
        }
    }

    for (int i = 0; i < input.length(); i++) {
        if (!charsNonUnique['z' - input.charAt(i)])
            return input.charAt(i);
    }

    return '?'; //example return of no character found
}

回答by Kostas Chalkias

If you are only interested for characters in the range a-z (lowercase as OP requested in comments), you can use this method that requires a minimum extra storage of two bits per character Vs a HashMap approach.

如果您只对 az 范围内的字符感兴趣（评论中要求的 OP 小写），您可以使用这种方法，该方法要求每个字符至少额外存储两位，而不是 HashMap 方法。

String charHolder;  // Holds 
String testString = "8uiuiti080t8xt8t";
char   testChar = ' ';
int count = 0;  

for (int i=0; i <= testString.length()-1; i++) {
    testChar = testString.charAt(i);

    for (int j=0; j < testString.length()-1; j++) {
        if (testChar == testString.charAt(j)) {
           count++;
        }
    }
    if (count == 1) { break; };
       count = 0;
}

System.out.println("The first not repeating character is " + testChar);

回答by JamesJ30t

Works for any type of characters.

适用于任何类型的字符。

import java.util.Scanner;

public class NonRepaeated1
{
  public static void main(String args[])
  {
    String str;
    char non_repeat=0;
    int len,i,j,count=0;

    Scanner s = new Scanner(System.in);
    str = s.nextLine();

    len = str.length();

    for(i=0;i<len;i++) 
    { 
      non_repeat=str.charAt(i); 
      count=1; 

      for(j=0;j<len;j++) 
      { 
        if(i!=j) 
        { 
          if(str.charAt(i) == str.charAt(j)) 
          { 
            count=0; 
            break; 
          } 
        } 
      } 

      if(count==1) 
        break; 
    } 
if(count == 1) 
System.out.print("The non repeated character is  : " + non_repeat); 

  }
}

回答by Shiva Sagan

import java.util.LinkedHashMap;
import java.util.Map;

public class getFirstNonRep {

public static char get(String s) throws Exception {
    if (s.length() == 0) {
        System.out.println("Fail");
        System.exit(0);
    } else {
        Map<Character, Integer> m = new LinkedHashMap<Character, Integer>();

        for (int i = 0; i < s.length(); i++) {
            if (m.containsKey(s.charAt(i))) {
                m.put(s.charAt(i), m.get(s.charAt(i)) + 1);
            } else {
                m.put(s.charAt(i), 1);
            }
        }
        for (Map.Entry<Character, Integer> hm : m.entrySet()) {
            if (hm.getValue() == 1) {
                return hm.getKey();
            }
        }
    }
    return 0;
}

public static void main(String[] args) throws Exception {

    System.out.print(get("Youssef Zaky"));

    }

 }

回答by Zok

public char firstNonRepeatedChar(String input) {
    char out = 0;
    int length = input.length();
    for (int i = 0; i < length; i++) {
        String sub1 = input.substring(0, i);
        String sub2 = input.substring(i + 1);
        if (!(sub1.contains(input.charAt(i) + "") || sub2.contains(input
                .charAt(i) + ""))) {
            out = input.charAt(i);
            break;
        }
    }
    return out;
}

This solution takes less space and less time, since we iterate the string only one time.

这个解决方案占用更少的空间和更少的时间，因为我们只迭代字符串一次。

回答by vishal Mishra

package com.test.util;

public class StringNoRepeat {

    public static void main(String args[]) {
        String st = "234123nljnsdfsdf41l";
        String strOrig=st;
        int i=0;
        int j=0;
        String st1="";
        Character ch=' ';
        boolean fnd=false;
        for (i=0;i<strOrig.length(); i++) {


            ch=strOrig.charAt(i);
            st1 = ch.toString();

            if (i==0)
                st = strOrig.substring(1,strOrig.length());
            else if (i == strOrig.length()-1)
            st=strOrig.substring(0, strOrig.length()-1);
            else 
                st=strOrig.substring(0, i)+strOrig.substring(i+1,strOrig.length());
            if (st.indexOf(st1) == -1) {
                fnd=true;
              j=i;
                break;  
            }
        }
        if (!fnd)
            System.out.println("The first no non repeated character");
        else
            System.out.println("The first non repeated character is " +strOrig.charAt(j));


    }

}

回答by Ravi chinnamanaidu

##代码##