给定一个字符串，在一次扫描中找到它的第一个非重复字符

Given a string, find the first non-repeating character in it. For example, if the input string is “GeeksforGeeks”, then output should be ‘f’.

给定一个字符串，查找其中的第一个非重复字符。例如，如果输入字符串是“geeksforgeek”，那么输出应该是“f”。

We can use string characters as index and build a count array. Following is the algorithm.

我们可以使用字符串字符作为索引，并构建一个计数数组。下面是该算法。

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

1)从左到右扫描字符串，构建计数数组或HashMap。再次，从左到右扫描字符串并检查每个字符的计数，如果发现一个元素的计数为1，请返回它。

Above algorithm is from GeeksForGeeks

上面的算法来自geeksforgeek

But It requires two scan of an array. I want to find first non-repeating character in only one scan. I implement above algorithms. Please check it also on Ideone

但它需要对数组进行两次扫描。我想在一次扫描中找到第一个非重复字符。我在上面实现的算法。请在Ideone上也检查一下

import java.util.HashMap;
import java.util.Scanner;

/**
 *
 * @author Neelabh
 */
public class FirstNonRepeatedCharacter {
    public static void main(String [] args){
        Scanner scan=new Scanner(System.in);
        String string=scan.next();
        int len=string.length();
        HashMap<Character, Integer> hashMap=new HashMap<Character, Integer>();
        //First Scan
        for(int i = 0; i <len;i++){
            char currentCharacter=string.charAt(i);
            if(!hashMap.containsKey(currentCharacter)){
                hashMap.put(currentCharacter, 1);
            }
            else{
                hashMap.put(currentCharacter, hashMap.get(currentCharacter)+1);
            }
        }
        // Second Scan
        boolean flag=false;
        char firstNonRepeatingChar = 0;
        for(int i=0;i<len;i++){
                char c=string.charAt(i);
                if(hashMap.get(c)==1){
                    flag=true;
                    firstNonRepeatingChar=c;
                    break;
                }
        }
        if(flag==true)
            System.out.println("firstNonRepeatingChar is "+firstNonRepeatingChar);
        else
            System.out.println("There is no such type of character");
    }    
}

GeeksforGeeks also suggest efficient method but I think It is also two scan. Following solution is from GeeksForGeeks

geeksforgeek也提出了有效的方法，但我认为它也是两种扫描方式。下面的解决方案来自geeksforgeek

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#define NO_OF_CHARS 256

// Structure to store count of a character and index of the first
// occurrence in the input string
struct countIndex {
   int count;
   int index;
};

/* Returns an array of above structure type. The size of
   array is NO_OF_CHARS */
struct countIndex *getCharCountArray(char *str)
{
   struct countIndex *count =
        (struct countIndex *)calloc(sizeof(countIndex), NO_OF_CHARS);
   int i;

   // This is First Scan

   for (i = 0; *(str+i);  i++)
   {
      (count[*(str+i)].count)++;

      // If it's first occurrence, then store the index
      if (count[*(str+i)].count == 1)
         count[*(str+i)].index = i;
   }
   return count;
}

/* The function returns index of the first non-repeating
    character in a string. If all characters are repeating
    then reurns INT_MAX */
int firstNonRepeating(char *str)
{
  struct countIndex *count = getCharCountArray(str);
  int result = INT_MAX, i;

  //Second Scan
  for (i = 0; i < NO_OF_CHARS;  i++)
  {
    // If this character occurs only once and appears
    // before the current result, then update the result
    if (count[i].count == 1 && result > count[i].index)
       result = count[i].index;
  }

  free(count); // To avoid memory leak
  return result;
}


/* Driver program to test above function */
int main()
{
  char str[] = "geeksforgeeks";
  int index =  firstNonRepeating(str);
  if (index == INT_MAX)
    printf("Either all characters are repeating or string is empty");
  else
   printf("First non-repeating character is %c", str[index]);
  getchar();
  return 0;
}

27 个解决方案

#1

You can store 2 arrays: count of each character and the first occurrence(and fill both of them during the first scan). Then the second scan will be unnecessary.

您可以存储两个数组:每个字符的计数和第一次出现(并在第一次扫描时填充它们)。那么第二次扫描就没有必要了。

#2

Use String functions of java then you find the solution in only one for loop The Example is show below

使用java的字符串函数，然后在一个for循环中找到解决方案，示例如下所示

import java.util.Scanner;
public class firstoccurance {
public static void main(String args[]){
char [] a ={'h','h','l','l','o'};
//Scanner sc=new Scanner(System.in);
String s=new String(a);//sc.next();
char c;
int i;
int length=s.length();
for(i=0;i<length;i++)
{
    c=s.charAt(i);
    if(s.indexOf(c)==s.lastIndexOf(c))
    {
        System.out.println("first non repeating char in a string   "+c);
        break;
    }
    else if(i==length-1)
    {
        System.out.println("no single char");
    }
}
}
}

#3

In following solution I declare one class CharCountAndPosition which stores firstIndex and frequencyOfchar. During the reading string characterwise, firstIndex stores the first encounter of character and frequencyOfchar stores the total occurrence of characters.

在下面的解决方案中，我声明了存储firstIndex和frequency的一类CharCountAndPosition。在读取字符串字符期间，firstIndex存储字符的第一次遇到，而char的频率存储字符的总出现次数。

We will make array of CharCountAndPosition step:1 and Initialize it step2.
During scanning the string, Initialize the firstIndex and frequencyOfchar for every character step3.
Now In the step4 check the array of CharCountAndPosition, find the character with frequency==1 and minimum firstIndex
Over all time complexity is O(n+256), where n is size of string. O(n+256) is equivalent to O(n) Because 256 is constant. Please find solution of this on ideone

我们将按步骤1建立CharCountAndPosition数组，并在步骤2中初始化它。在扫描字符串时，为每个字符step3初始化firstIndex和frequencyOfchar。现在在步骤4中检查CharCountAndPosition的数组，找到频率=1并且在所有时间复杂度中最小firstIndex的字符是O(n+256)，其中n是字符串的大小。O(n+256)等于O(n)因为256是常数。请在ideone上找到解决办法

public class FirstNonRepeatedCharacterEfficient {
        public static void main(String [] args){
            // step1: make array of CharCountAndPosition.
            CharCountAndPosition [] array=new CharCountAndPosition[256];

            // step2: Initialize array with object of CharCountAndPosition. 
            for(int i=0;i<256;i++)
            {
                array[i]=new CharCountAndPosition();
            }

            Scanner scan=new Scanner(System.in);
            String str=scan.next();
            int len=str.length();
            // step 3
            for(int i=0;i<len;i++){
                char c=str.charAt(i);
                int index=c-'a';            
                int frequency=array[index].frequencyOfchar;
                if(frequency==0)
                    array[index].firstIndex=i;
                array[index].frequencyOfchar=frequency+1;    
                //System.out.println(c+" "+array[index].frequencyOfchar);
            }
            boolean flag=false;
            int firstPosition=Integer.MAX_VALUE;
            for(int i=0;i<256;i++){   

                // Step4         
                if(array[i].frequencyOfchar==1){
                    //System.out.println("character="+(char)(i+(int)'a'));
                    if(firstPosition> array[i].firstIndex){                    
                        firstPosition=array[i].firstIndex;
                        flag=true;
                    }
                }            
            }
            if(flag==true)
                System.out.println(str.charAt(firstPosition));
            else
                System.out.println("There is no such type of character");
        } 
    }
    class CharCountAndPosition{
        int firstIndex;
        int frequencyOfchar;
    }

#4

A solution in javascript with a lookup table:

一个带有查找表的javascript解决方案:

var sample="It requires two scan of an array I want to find first non repeating character in only one scan";
var sampleArray=sample.split("");
var table=Object.create(null);
sampleArray.forEach(function(char,idx){
  char=char.toLowerCase();
  var pos=table[char];
  if(typeof(pos)=="number"){
    table[char]=sampleArray.length;  //a duplicate found; we'll assign some invalid index value to this entry and discard these characters later
    return;
  }
  table[char]=idx;  //index of first occurance of this character
});
var uniques=Object.keys(table).filter(function(k){
  return table[k]<sampleArray.length; 
}).map(function(k){
  return {key:k,pos:table[k]};
});
uniques.sort(function(a,b){
  return a.pos-b.pos;
});
uniques.toSource();         //[{key:"q", pos:5}, {key:"u", pos:6}, {key:"d", pos:46}, {key:"p", pos:60}, {key:"g", pos:66}, {key:"h", pos:69}, {key:"l", pos:83}]
(uniques.shift()||{}).key;  //q

#5

Following C prog, add char specific value to 'count' if char didn't occurred before, removes char specific value from 'count' if char had occurred before. At the end I get a 'count' that has char specific value which indicate what was that char!

在C prog之后，如果之前没有出现char，就向'count'添加char特定值，如果之前没有出现过char，则从'count'中删除char特定值。最后，我得到一个“count”，它具有char特有的值，该值指示char!

//TO DO:
//If multiple unique char occurs, which one is occurred before? 
//Is is possible to get required values (1,2,4,8,..) till _Z_ and _z_?

#include <stdio.h>

#define _A_ 1
#define _B_ 2
#define _C_ 4 
#define _D_ 8
//And so on till _Z

//Same for '_a' to '_z'

#define ADDIFNONREP(C) if(count & C) count = count & ~C; else count = count | C; break;

char getNonRepChar(char *str)
{
        int i = 0, count = 0;
        for(i = 0; str[i] != '\0'; i++)
        {
                switch(str[i])
                {
                        case 'A':
                                ADDIFNONREP(_A_);
                        case 'B':
                                ADDIFNONREP(_B_);
                        case 'C':
                                ADDIFNONREP(_C_);
                        case 'D':
                                ADDIFNONREP(_D_);
                        //And so on
                        //Same for 'a' to 'z'
                }
        }
        switch(count)
        {
                case _A_:
                        return 'A';
                case _B_:
                        return 'B';
                case _C_:
                        return 'C';
                case _D_:
                        return 'D';
                //And so on
                //Same for 'a' to 'z'
        }
}

int main()
{
        char str[] = "ABCDABC";
        char c = getNonRepChar(str);
        printf("%c\n", c); //Prints D
        return 0;
} 

#6

You can maintain a queue of keys as they are added to the hash map (you add your key to the queue if you add a new key to the hash map). After string scan, you use the queue to obtain the order of the keys as they were added to the map. This functionality is exactly what Java standard library class OrderedHashMap does.

您可以在将键添加到哈希映射时维护一个密钥队列(如果向哈希映射添加新键，则向队列添加密钥)。在字符串扫描之后，使用队列获取添加到映射中的键的顺序。这个功能正是Java标准库类OrderedHashMap所做的。

#7

Here is my take on the problem.

这是我对这个问题的看法。

Iterate through string. Check if hashset contains the character. If so delete it from array. If not present just add it to the array and hashset.

遍历字符串。检查hashset是否包含字符。如果是，从数组中删除它。如果不是present，就将它添加到数组和hashset中。

NSMutableSet *repeated = [[NSMutableSet alloc] init]; //Hashset

NSMutableArray *nonRepeated = [[NSMutableArray alloc] init]; //Array

for (int i=0; i<[test length]; i++) {

    NSString *currentObj = [NSString stringWithFormat:@"%c", [test characterAtIndex:i]]; //No support for primitive data types.

    if ([repeated containsObject:currentObj]) {
        [nonRepeated removeObject:currentObj];// in obj-c nothing happens even if nonrepeted in nil
        continue;
    }

    [repeated addObject:currentObj];

    [nonRepeated addObject:currentObj];

}

NSLog(@"This is the character %@", [nonRepeated objectAtIndex:0]);

#8

If you can restrict yourself to strings of ASCII characters, I would recommend a lookup table instead of a hash table. This lookup table would have only 128 entries.

如果您可以将自己限制为ASCII字符的字符串，那么我将推荐一个查找表，而不是散列表。这个查找表将只有128个条目。

A possible approach would be as follows.

一种可能的方法如下。

We start with an empty queue Q (may be implemented using linked lists) and a lookup table T. For a character ch, T[ch] stores a pointer to a queue node containing the character ch and the index of the first occurrence of ch in the string. Initially, all entries of T are NULL.

我们从一个空队列Q(可以使用链表实现)和一个查找表T开始。最初，T的所有元素都是空的。

Each queue node stores the character and the first occurrence index as specified earlier, and also has a special boolean flag named removed which indicates that the node has been removed from the queue.

每个队列节点按照前面指定的方式存储字符和第一个出现索引，并且还具有一个特殊的boolean标记，该标记表示该节点已从队列中删除。

Read the string character by character. If the i^th character is ch, check if T[ch] = NULL. If so, this is the first occurrence of ch in the string. Then add a node for ch containing the index i to the queue.

逐字符读取字符串。如果第i个字符是ch，则检查T[ch]是否为NULL。如果是，这是弦中第一个出现的ch。然后为ch添加一个包含索引i的节点到队列中。

If T[ch] is not NULL, this is a repeating character. If the node pointed to by T[ch] has already been removed (i.e. the removed flag of the node is set), then nothing needs to be done. Otherwise, remove the node from the queue by manipulating the pointers of the previous and next nodes. Also set the removed flag of the node to indicate that the node is now removed. Note that we do not free/delete the node at this stage, nor do we set T[ch] back to NULL.

如果T[ch]不是NULL，这是一个重复字符。如果T[ch]所指向的节点已经被删除(即设置节点的已删除标志)，则不需要做任何事情。否则，通过操作前一个和下一个节点的指针从队列中删除节点。还设置节点的移除标记，以表明该节点已被删除。注意，我们在此阶段没有释放/删除节点，也没有将T[ch]设置为NULL。

If we proceed in this way, the nodes for all the repeating characters will be removed from the queue. The removed flag is used to ensure that no node is removed twice from the queue if the character occurs more than two times.

如果以这种方式进行，所有重复字符的节点将从队列中删除。删除的标志用于确保如果字符出现超过两次，则不会从队列中删除任何节点。

After the string has been completely processed, the first node of the linked list will contain the character code as well as the index of the first non-repeating character. Then, the memory can be freed by iterating over the entries of lookup table T and freeing any non-NULL entries.

当字符串被完全处理后，链表的第一个节点将包含字符代码以及第一个非重复字符的索引。然后，可以通过遍历查找表T的条目并释放任何非空条目来释放内存。

Here is a C implementation. Here, instead of the removed flag, I set the prev and next pointers of the current node to NULL when it is removed, and check for that to see if a node has already been removed.

这是一个C实现。这里，我将当前节点的prev和下一个指针设置为NULL，而不是删除标记，并检查该节点是否已经被删除。

#include <stdio.h>
#include <stdlib.h>

struct queue_node {
    int ch;
    int index;
    struct queue_node *prev;
    struct queue_node *next;
};

void print_queue (struct queue_node *head);

int main (void)
{
    int i;
    struct queue_node *lookup_entry[128];
    struct queue_node *head;
    struct queue_node *last;
    struct queue_node *cur_node, *prev_node, *next_node;

    char str [] = "GeeksforGeeks";

    head = malloc (sizeof (struct queue_node));
    last = head;
    last->prev = last->next = NULL;

    for (i = 0; i < 128; i++) {
        lookup_entry[i] = NULL;
    }

    for (i = 0; str[i] != '\0'; i++) {
        cur_node = lookup_entry[str[i]];

        if (cur_node != NULL) {
            /* it is a repeating character */
            if (cur_node->prev != NULL) {
                /* Entry has not been removed. Remove it from the queue. */
                prev_node = cur_node->prev;
                next_node = cur_node->next;

                prev_node->next = next_node;
                if (next_node != NULL) {
                    next_node->prev = prev_node;
                } else {
                    /* Last node was removed */
                    last = prev_node;
                }

                cur_node->prev = NULL;
                cur_node->next = NULL;
                /* We will not free the node now. Instead, free
                 * all nodes in a single pass afterwards.
                 */ 
            }
        } else {
            /* This is the first occurence - add an entry to the queue */
            struct queue_node *newnode = malloc (sizeof(struct queue_node));

            newnode->ch = str[i];
            newnode->index = i;
            newnode->prev = last;
            newnode->next = NULL;
            last->next = newnode;
            last = newnode;

            lookup_entry[str[i]] = newnode;
        }
        print_queue (head);
    }

    last = head->next;
    while (last != NULL) {
        printf ("Non-repeating char: %c at index %d.\n", last->ch, last->index);
        last = last->next;
    }

    /* Free the queue memory */
    for (i = 0; i < 128; i++) {
        if (lookup_entry[i] != NULL) {
            free (lookup_entry[i]);
            lookup_entry[i] = NULL;
        }
    }
    free (head);

    return (0);
}

void print_queue (struct queue_node *head) {
    struct queue_node *tmp = head->next;

    printf ("Queue: ");
    while (tmp != NULL) {
        printf ("%c:%d ", tmp->ch, tmp->index);
        tmp = tmp->next;
    }
    printf ("\n");
}

#9

Instead of making things more and more complex, I can use three for loops to tackle this.

我可以用三个for循环来解决这个问题，而不是让事情变得越来越复杂。

class test{
    public static void main(String args[]){
        String s="STRESST";//Your input can be given here.
        char a[]=new char[s.length()];
    for(int i=0;i<s.length();i++){
        a[i]=s.charAt(i);
    }

    for(int i=0;i<s.length();i++){
        int flag=0;
       for(int j=0;j<s.length();j++){
            if(a[i]==a[j]){
             flag++;
            }
       }

        if(flag==1){
         System.out.println(a[i]+" is not repeated");
         break;
        }
    }
    }
}

I guess it will be helpful for people who are just gonna look at the logic part without any complex methods used in the program.

我想这对那些只看逻辑部分而不使用任何复杂方法的人是有帮助的。

#10

This can be done in one Scan using the substring method. Do it like this:

这可以使用子字符串方法在一次扫描中完成。这样做:

String str="your String";<br>
String s[]= str.split("");<br>
int n=str.length();<br>
int i=0;<br><br>

for(String ss:s){
  if(!str.substring(i+1,n).contains(ss)){
    System.out.println(ss);
  }
}

This will have the lowest complexity and will search for it even without completing one full scan.

这将具有最低的复杂性，并将搜索它，即使没有完成一次完整的扫描。

#11

Add each character to a HashSet and check whether hashset.add() returns true, if it returns false ,then remove the character from hashset. Then getting the first value of the hashset will give you the first non repeated character. Algorithm:

将每个字符添加到一个HashSet中，并检查HashSet . Add()是否返回true，如果返回false，则从HashSet中删除该字符。然后获取hashset的第一个值将给您第一个非重复字符。算法:

 for(i=0;i<str.length;i++)
{
 HashSet hashSet=new HashSet<>()
 if(!hashSet.add(str[i))
   hashSet.remove(str[i])
 }
 hashset.get(0) will give the non repeated character.

#12

i have this program which is more simple, this is not using any data structures

我有一个更简单的程序，它不使用任何数据结构

public static char findFirstNonRepChar(String input){
    char currentChar = '\0';
    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;
}

#13

A simple (non hashed) version...

一个简单的(非散列)版本…

public static String firstNRC(String s) {
    String c = "";
    while(s.length() > 0) {
        c = "" + s.charAt(0);
        if(! s.substring(1).contains(c)) return c;
        s = s.replace(c, "");
    }
    return "";
}

or

或

public static char firstNRC(String s) {
    s += " ";
    for(int i = 0; i < s.length() - 1; i++) 
        if( s.split("" + s.charAt(i)).length == 2 ) return s.charAt(i);
    return ' ';
}

#14

//This is the simple logic for finding first non-repeated character....

/ /这是一个简单的逻辑寻找第一个non-repeated字符....

public static void main(String[] args) {

        String s = "GeeksforGeeks";

        for (int i = 0; i < s.length(); i++) {

            char begin = s.charAt(i);
            String begin1 = String.valueOf(begin);
            String end = s.substring(0, i) + s.substring(i + 1);

            if (end.contains(begin1));
            else {
                i = s.length() + 1;
                System.out.println(begin1);
            }

        }

    }

#15

@Test
public void testNonRepeadLetter() {
    assertEquals('f', firstNonRepeatLetter("GeeksforGeeks"));
    assertEquals('I', firstNonRepeatLetter("teststestsI"));
    assertEquals('1', firstNonRepeatLetter("123aloalo"));
    assertEquals('o', firstNonRepeatLetter("o"));

}

private char firstNonRepeatLetter(String s) {
    if (s == null || s.isEmpty()) {
        throw new IllegalArgumentException(s);
    }
    Set<Character> set = new LinkedHashSet<>();

    for (int i = 0; i < s.length(); i++) {
        char charAt = s.charAt(i);
        if (set.contains(charAt)) {
            set.remove(charAt);
        } else {
            set.add(charAt);
        }
    }
    return set.iterator().next();
}

#16

here is a tested code in java. note that it is possible that no non repeated character is found, and for that we return a '0'

下面是java中测试的代码。注意，可能没有发现非重复字符，为此我们返回一个'0'

// find first non repeated character in a string
static char firstNR( String str){
    int i, j, l;
    char letter;
    int[] k = new int[100];

    j = str.length();

    if ( j > 100) return '0';

    for (i=0; i< j; i++){
        k[i] = 0;
    }

    for (i=0; i<j; i++){
        for (l=0; l<j; l++){
            if (str.charAt(i) == str.charAt(l))
                k[i]++;
        }
    }

    for (i=0; i<j; i++){
        if (k[i] == 1)
            return str.charAt(i);
    }

    return '0';

#17

Here is the logic to find the first non-repeatable letter in a String.

这里是查找字符串中第一个不可重复字母的逻辑。

String name = "TestRepeat";
        Set <Character> set = new LinkedHashSet<Character>();
        List<Character> list = new ArrayList<Character>();
        char[] ch = name.toCharArray();
        for (char c :ch) {
            set.add(c);
            list.add(c);
        }
        Iterator<Character> itr1 = set.iterator();
        Iterator<Character> itr2= list.iterator();

        while(itr1.hasNext()){
            int flag =0;
            Character  setNext= itr1.next();
            for(int i=0; i<list.size(); i++){
                Character listNext= list.get(i);
                if(listNext.compareTo(setNext)== 0){
                    flag ++;
                }
            }

            if(flag==1){
                System.out.println("Character: "+setNext);
                break;
            }
        }

#18

it is very easy....you can do it without collection in java..

它是非常容易....您可以不使用java进行收集。

public class FirstNonRepeatedString{

    public static void main(String args[]) {
        String input ="GeeksforGeeks";
        char process[] = input.toCharArray();
        boolean status = false;
        int index = 0;
        for (int i = 0; i < process.length; i++) {
            for (int j = 0; j < process.length; j++) {

                if (i == j) {
                    continue;
                } else {
                    if (process[i] == process[j]) {
                        status = false;
                        break;
                    } else {
                        status = true;
                        index = i;
                    }
                }

            }
             if (status) {
            System.out.println("First non-repeated string is : " + process[index]);
            break;
        } 
        }
    }
}

#19

We can create LinkedHashMap having each character from the string and it's respective count. And then traverse through the map when you come across char with count as 1 return that character. Below is the function for the same.

我们可以创建一个LinkedHashMap，其中包含字符串中的每个字符，并且它是各自的计数。当你遇到带有count为1的字符返回那个字符时，再遍历映射。下面是相同的函数。

private static char findFirstNonRepeatedChar(String string) {
    LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
    for(int i=0;i< string.length();i++){
        if(map.containsKey(string.charAt(i)))
            map.put(string.charAt(i),map.get(string.charAt(i))+1);
        else
            map.put(string.charAt(i),1);
    }

    for(Entry<Character,Integer> entry : map.entrySet()){
        if(entry.getValue() == 1){
            return entry.getKey();
        }
    }
    return ' ';
}

#20

One Pass Solution. I have used linked Hashmap here to maintain the insertion order. So I go through all the characters of a string and store it values in Linked HashMap. After that I traverse through the Linked Hash map and whichever first key will have its value equal to 1, I will print that key and exit the program.

通过一个解决方案。我在这里使用了链接Hashmap来维持插入顺序。我遍历字符串的所有字符并将其值存储在链接的HashMap中。然后我遍历链接的散列映射，无论哪个第一个键的值为1，我将打印该键并退出程序。

    import java.util.*;
    class demo
    {
    public static void main(String args[])
     {
          String str="GeekGsQuizk";
          HashMap  <Character,Integer>hm=new LinkedHashMap<Character,Integer>();

                    for(int i=0;i<str.length();i++)
                      {
                       if(!hm.containsKey(str.charAt(i)))
                       hm.put(str.charAt(i),1);
                       else
                       hm.put(str.charAt(i),hm.get(str.charAt(i))+1);
                      }

           for (Character key : hm.keySet())
               {
                      if(hm.get(key)==1)
                   { 
                   System.out.println(key);
                   System.exit(0) ; 
                   }         

               }

         }
       }

#21

I know this comes one year late, but I think if you use LinkedHashMap in your solution instead of using a HashMap, you will have the order guaranteed in the resulting map and you can directly return the key with the corresponding value as 1.

我知道这晚了一年，但是我认为如果你在你的解决方案中使用LinkedHashMap而不是使用HashMap，你会在结果映射中得到保证的顺序，你可以直接返回键值为1。

Not sure if this is what you wanted though as you will have to iterate over the map (not the string) after you are done populating it - but just my 2 cents.

不确定这是否是您想要的，因为您将不得不在填充完成之后遍历映射(而不是字符串)——但只是我的2分。

Regards,

问候,

-Vini

-Vini

#22

Finding first non-repeated character in one pass O(n ) , without using indexOf and lastIndexOf methods

在一个传递O(n)中查找第一个非重复字符，而不使用indexOf和lastIndexOf方法。

package nee.com;
public class FirstNonRepeatedCharacterinOnePass {

    public static void printFirstNonRepeatedCharacter(String str){
        String strToCaps=str.toUpperCase();
        char ch[]=strToCaps.toCharArray();
        StringBuilder sb=new StringBuilder();
        // ASCII range for A-Z ( 91-65 =26)
        boolean b[]=new boolean[26];

        for(int i=0;i<ch.length;i++){
            if(b[ch[i]-65]==false){
                b[ch[i]-65]=true;               
            }
            else{
                //add repeated char to StringBuilder
                sb.append(ch[i]+"");
            }
        }
        for(int i=0;i<ch.length;i++){
            // if char is not there in StringBuilder means it is non repeated
            if(sb.indexOf(ch[i]+"")==-1){
                System.out.println(" first non repeated  in lower case ...."+Character.toLowerCase((ch[i])));
            break;
            }               
        }

    }
    public static void main(String g[]){
        String str="abczdabddcn";
        printFirstNonRepeatedCharacter(str);
    }

}

#23

I did the same using LinkedHashSet. Following is the code snippet:

我也用了LinkedHashSet。下面是代码片段:

System.out.print("Please enter the string :");
str=sc.nextLine();
if(null==str || str.equals("")) {
   break;
}else {
   chArr=str.toLowerCase().toCharArray();
   set=new LinkedHashSet<Character>();
   dupSet=new LinkedHashSet<Character>();
   for(char chVal:chArr) {
    if(set.contains(chVal)) {
        dupSet.add(chVal);
    }else {
        set.add(chVal);
    }
   }
   set.removeAll(dupSet);
   System.out.println("First unique :"+set.toArray()[0]);
}

#24

You can find this question here

你可以在这里找到这个问题

For code of the below algorithm refer this link (My implementation with test cases)

下面算法的代码请参考这个链接(我的测试用例实现)

Using linkedlist in combination with hashMap

与hashMap结合使用linkedlist

I have a solution which solves it in O(n) time One array pass and O(1) space Inreality -> O(1) space is O(26) space

我有一个解决方案，它在O(n)时间内解决了一个数组传递和O(1)空间的现实-> O(1)空间是O(26)空间。

Algorithm

算法

1) every time you visit a character for the first time

每次你第一次去拜访一个角色

Create a node for the linkedList(storing that character).Append it at the end of the lnkedList.Add an entry in the hashMap storing for recently appended charater the address of the node in the linked list that was before that character.If character is appended to an empty linked list store null for vale in hash map.

为linkedList创建一个节点(存储该字符)。在lnkedList的末尾添加它。在hashMap中添加一个条目，用于为最近添加的charater存储在该字符之前的链接列表中的节点地址。如果字符被追加到一个空的链接列表中，在哈希映射中为谷值存储null。

2) Now if you encounter the same charactter again

如果你再遇到同样的角色

Remove that element from the linkedlist using the address stored in the hash map and now you have to update for the element that was after the deleted element ,the previous element for it. Make it equal to the previous element of the deleted element.

使用存储在散列映射中的地址从linkedlist中删除该元素，现在必须更新在已删除元素之后的元素，即之前的元素。使它等于已删除元素的前一个元素。

Complexity Analysis

复杂性分析

LinkedlIst add element -> O(1)

LinkedlIst添加元素-> O(1)

LinkedlIst delete element -> O(1)

LinkedlIst删除元素-> O(1)

HashMap -> O(1)

HashMap - > O(1)

space O(1)

空间O(1)

pass -> one in O(n)

pass -> 1 in O(n)

    #include<bits/stdc++.h>
    using namespace std;

    typedef struct node
    {
        char ch;
        node *next;
    }node;




    char firstNotRepeatingCharacter(string &s)
    {
      char ans = '_';
      map<char,node*> mp;//hash map atmost may consume O(26) space
      node *head = NULL;//linkedlist atmost may consume O(26) space
      node *last;// to append at last in O(1)
      node *temp1 = NULL;
      node *temp2 = new node[1];
      temp2->ch = '$';
      temp2->next = NULL;
      //This is my one pass of array//
      for(int i = 0;i < s.size();++i)
      {
        //first occurence of character//
        if(mp.find(s[i]) == mp.end())
        {
          node *temp = new node[1];
          temp->ch = s[i];
          temp->next = NULL;
          if(head == NULL)
          {
            head = temp;
            last = temp;
            mp.insert(make_pair(s[i],temp1));
          }
          else
          {
            last->next = temp;
            mp.insert(make_pair(s[i],last));
            last = temp; 
          }
        }
        //Repeated occurence//
        else
        {
          node *temp = mp[s[i]];
          if(mp[s[i]] != temp2)
          {
            if(temp == temp1)
            {
              head = head->next;
              if((head)!=NULL){mp[head->ch] = temp1;}
              else last = head;
              mp[s[i]] = temp2;
            }
            else if((temp->next) != NULL)
            {
              temp->next = temp->next->next;
              if((temp->next) != NULL){mp[temp->next->ch] = temp;}
              else last = temp;
              mp[s[i]] = temp2;
            }
            else
            {
              ;
            }
         }
        }
      if(head == NULL){;}
      else {ans = head->ch;}
      return ans;
    }

    int main()
    {
      int T;
      cin >> T;
      while(T--)
      {
      string str;
      cin >> str;
      cout << str << " ->  " << firstNotRepeatingCharacter(str)<< endl;
      }
      return 0;
    }

#25

Requires one scan only.

只需要一个扫描。

Uses a deque (saves char) and a hashmap (saves char->node). On repeating char, get char's node in deque using hashmap and remove it from deque (in O(1) time) but keep the char in hashmap with null node value. peek() gives the 1st unique character.

使用deque(保存char)和hashmap(保存char->节点)。在重复char时，使用hashmap在deque中获取char节点，并将其从deque中删除(在O(1)时间内)，但在hashmap中保留null节点值。peek()给出第一个唯一字符。

[pseudocode]
char? findFirstUniqueChar(s):
    if s == null:
        throw
    deque<char>() dq = new
    hashmap<char, node<char>> chToNodeMap = new
    for i = 0, i < s.length(), i++:
        ch = s[i]
        if !chToNodeMap.hasKey(ch):
            chToNodeMap[ch] = dq.enqueue(ch)
        else:
            chNode = chToNodeMap[ch]
            if chNode != null:
                dq.removeNode(chNode)
                chToNodeMap[ch] = null
    if dq.isEmpty():
        return null
    return dq.peek()

// deque interface
deque<T>:
    node<T> enqueue(T t)
    bool removeNode(node<T> n)
    T peek()
    bool isEmpty()

#26

The string is scanned only once; other scans happen on counts and first appearance arrays, which are generally much smaller in size. Or at least below approach is for cases when string is much larger than character set the string is made from.

该字符串只扫描一次;其他的扫描发生在计数和第一个外观阵列上，通常小得多。或者至少下面的方法适用于字符串比字符集大得多的情况。

Here is an example in golang:

这里有一个golang的例子:

package main

import (
    "fmt"
)

func firstNotRepeatingCharacter(s string) int {

    counts := make([]int, 256)
    first := make([]int, 256)

    // The string is parsed only once 
    for i := len(s) - 1; i >= 0; i-- {
        counts[s[i]]++
        first[s[i]] = i
    }

    min := 0
    minValue := len(s) + 1

    // Now we are parsing counts and first slices
    for i := 0; i < 256; i++ {
        if counts[i] == 1 && first[i] < minValue {
            minValue = first[i]
            min = i
        }
    }

    return min

}

func main() {

    fmt.Println(string(firstNotRepeatingCharacter("fff")))
    fmt.Println(string(firstNotRepeatingCharacter("aabbc")))
    fmt.Println(string(firstNotRepeatingCharacter("cbbc")))
    fmt.Println(string(firstNotRepeatingCharacter("cbabc")))

}

go playground

去操场

#27

Question : Find First Non Repeating Character or First Unique Character:

问题:找到第一个非重复字符或第一个唯一字符:

The code itself is understandable.

代码本身是可以理解的。

public class uniqueCharacter1 {
    public static void main(String[] args) {
        String a = "GiniGinaProtijayi";

        firstUniqCharindex(a);
    }

    public static void firstUniqCharindex(String a) {
        int count[] = new int[256];
        for (char ch : a.toCharArray()) {
            count[ch]++;
        } // for

        for (int i = 0; i < a.length(); i++) {
            char ch = a.charAt(i);
            if (count[ch] == 1) {
                System.out.println(i);// 8
                System.out.println(a.charAt(i));// p
                break;
            }
        }

    }// end1
}

In Python:

在Python中:

def firstUniqChar(a):
  count = [0] * 256
  for i in a: count[ord(i)] += 1 
  element = ""
  for items in a:
      if(count[ord(items) ] == 1):
          element = items ;
          break
  return element


a = "GiniGinaProtijayi";
print(firstUniqChar(a)) # output is P