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

Question

给定一个字符串,找到其中的第一个非重复字符.例如,如果输入字符串是"GeeksforGeeks",则输出应为"f".

我们可以使用字符串字符作为索引并构建计数数组.以下是算法.

1)从左到右扫描字符串并构造计数数组或HashMap.
2)再次,从左到右扫描字符串并检查每个字符的计数,如果找到一个计数为1的元素,则将其返回.

以上算法来自GeeksForGeeks

但它需要两次扫描一个数组.我想在一次扫描中找到第一个非重复字符.我实现上面的算法.请在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也提出了有效的方法,但我认为这也是两次扫描.以下解决方案来自GeeksForGeeks

#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;
}

Answer 1

您可以存储2个数组:每个字符的计数和第一次出现(并在第一次扫描期间填充它们).然后第二次扫描将是不必要的.

Answer 2

使用Java的String函数，然后仅在一个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");
    }
}
}
}