给定一个字符串，只能在一个扫描中找到它的第一个不重复的字符 [英] Given a string, find its first non-repeating character in only One scan
问题描述
我们可以使用字符串字符作为索引并构建计数数组。以下是算法。
1）从左到右扫描字符串，构造计数数组或HashMap。
2）再次扫描字符串从左到右，并检查每个
字符的计数，如果您发现一个元素的计数为1，返回它。
以上算法来自 GeeksForGeeks
但是它需要对数组进行两次扫描。我只想在一次扫描中找到第一个不重复的字符。我实现了上述算法。 请查看Ideone
import java.util.HashMap;
import java.util.Scanner;
/ **
*
* @author Neelabh
* /
public class FirstNonRepeatedCharacter {
public static void main args）{
扫描仪扫描=新扫描仪（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
if（！hashMap.containsKey（currentCharacter））{
hashMap.put（currentCharacter，1）;
}
else {
hashMap.put（currentCharacter，hashMap.get（currentCharacter）+1）;
}
}
// Second Scan
boolean flag = false;
char firstNonRepeatingChar = 0; （int i = 0; 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（没有这样的字符类型）;
}
}
GeeksforGeeks还提出了有效的方法，但我认为也是两次扫描以下解决方案来自 GeeksForGeeks
#include< stdlib.h>
#include< stdio.h>
#include< limits.h>
#define NO_OF_CHARS 256
//结构存储第一个
//的字符和索引的计数//在输入字符串中出现
struct countIndex {
int count;
int index;
};
/ *返回上述结构类型的数组。
数组的大小是NO_OF_CHARS * /
struct countIndex * getCharCountArray（char * str）
{
struct countIndex * count =
（struct countIndex *）calloc sizeof（countIndex），NO_OF_CHARS）;
int i;
//这是第一次扫描
for（i = 0; *（str + i）; i ++）
{
（str + i）]。count）++;
//如果是第一次出现，则存储索引
if（count [*（str + i）]。count == 1）
count [*（str + i）]。index = i;
}
返回计数;
}
/ *该函数返回字符串中第一个不重复
字符的索引。如果所有字符都重复
，那么重新打开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（count [i] .count == 1&& result> count [i] .index）
result = count [我]
}
免费（计数）; //避免内存泄漏
返回结果;
}
/ *用于测试上述函数的驱动程序* /
int main（）
{
char str [] =极客
int index = firstNonRepeating（str）;
if（index == INT_MAX）
printf（所有字符都重复或字符串为空）;
else
printf（第一个非重复字符为％c，str [index]）;
getchar（）;
return 0;
}
您可以存储2个数组：每个字符的计数和第一次出现（并且在第一次扫描期间填充它们）。那么第二次扫描是不必要的。
Given a string, find the first non-repeating character in it. For example, if the input string is "GeeksforGeeks", then output should be ‘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.
Above algorithm is from GeeksForGeeks
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
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
#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;
}
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.
这篇关于给定一个字符串，只能在一个扫描中找到它的第一个不重复的字符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
