对于一个字符串,请设计一个高效算法,找到第一次重复出现的字符。
给定一个字符串(不一定全为字母)A及它的长度n。请返回第一个重复出现的字符。保证字符串中有重复字符,字符串的长度小于等于500。
测试样例:
"qywyer23tdd",11
返回:y
三种方法(都是基于哈希思想) ① HashMap ② HashSet ③ 数组Hash package nowcoder.codingPro; import java.util.HashMap; import java.util.HashSet; public class 去哪儿_首个重复字符 { /** * * * HashMap解 * * @param A * @param n * @return */ public char findFirstRepeat_1(String A, int n) { HashMap<Character, Integer> hm = new HashMap<Character, Integer>(); char[] charArray = A.toCharArray(); for (int i = 0; i < charArray.length; i++) { if (hm.get(charArray[i]) == null) { hm.put(charArray[i], 1); } else { return charArray[i]; } } return '\n'; } /** * * HashSet解 * * @param A * @param n * @return */ public char findFirstRepeat_2(String A, int n) { HashSet<Character> hm = new HashSet<Character>(); char[] charArray = A.toCharArray(); for (int i = 0; i < charArray.length; i++) { if (hm.add(charArray[i])) { } else { return charArray[i]; } } return '\n'; } /** * * 数组模拟hash 高效解法 * * @param A * @param n * @return */ public char findFirstRepeat_3(String A, int n) { char[] charArray = A.toCharArray(); int[] hashChar = new int[256]; // ASCII 范围 for (int i=0; i<charArray.length; i++) { if (hashChar[charArray[i] - '0'] == 0) { hashChar[charArray[i] - '0'] = 1; } else { return charArray[i]; } } return '\n'; } }
/*C/C++不支持数组整体赋值,可以在声明数组时整体初始化。 无论数组有多大,全部初始化为0的操作很简单,如int a[3000]={0};就可以将a的3000个元素全部置0; 若要赋其他值,例如全部赋值为7,写成int a[3000]={7};则不行,这只给a[0]赋值为7,其余的都是0。*/ class FirstRepeat { public: char findFirstRepeat(string A, int n) { int a[256] = {0}; int i; if( n==0 || A.size() == 0 ){ return 0; } else{ for(i=0;i<n;i++){ if( !a[ A[i] ] ) a[ A[i] ] = 1; else break; } } return A[i]; } }; //遍历原数组,新建数组存储不重复元素 class FirstRepeat { public: char findFirstRepeat(string A, int n) { char a[500]; int i,j,x=0,z=0; for(i=0;i<n;i++){ for(j=0;j<x;j++){ if(a[j] == A[i]){ z = 1; break; } } if(z == 1) break; if(j == x) a[x++] = A[i]; } return A[i]; } };
//使用set,依次压入元素,来判断第一个在set中出现的字符,符合题意 char findFirstRepeat(string A, int n) { // write code here set<char> chset; int i; for(i=0; i<n; ++i){ if(chset.find(A[i]) == chset.end()) chset.insert(A[i]); else break; } return A[i]; } //第一次没看清题意,返回的是字符串中最前面的重复字符,如abba,返回了a,不合题意 char findFirstRepeat(string A, int n) { // write code here int i; string::size_type idx = 0; for(i=0; i<n-1; ++i){ string tmp = A.substr(i, 1); if((idx = A.find_first_of(tmp, i+1)) != string::npos) break; } return A[idx]; }
#include <iostream> using namespace std ; class FirstRepeat{ public: char find_first_repeat(char *s,int n){ int hash[500] = {0} ; if(s == NULL || n == 0){ return 0; } int i ; for(i=0;i<n;i++){ if(hash[s[i]] != 0){ return s[i]; }else{ hash[s[i]] = 1 ; } } return s[i] ; } }; int main(){ FirstRepeat *firstrepeat = new FirstRepeat() ; char *s = "qywyer23tdd" ; char c = firstrepeat->find_first_repeat(s,11) ; cout<<c<<endl ; return 0 ; }
char Findfirstrepeat(string A,int n) { map <char,int>has; pair<map<char,int>::iterator,bool> Insert; char c; for(int i=0;i<n;i++) { c=A[i]; Insert=has.insert(pair<char,int>(c,1)); if(Insert.second==0)return c; } }